Нужен алгоритм (логика) для наилучшей комбинации сумм из многогруппового списка

Сокращение:
Учитывая экземпляр проблемы суммы подмножества в форме (S,k), создайте экземпляр этой проблемы в форме (G1,G2,...,Gn,k), где Gi - это одноэлементная группа с элементом i из S и k это число, которое мы ищем.

Доказательство:
Сумма подмножества -> Эта проблема: предположим, что существует подмножество S'={si_1,si_2,...,si_m} такое, что si_1 + si_2 + ... + si_m = k, затем, выбирая один элемент из каждой группы: Gi_1, Gi_2, ... , Gi_m, они суммируют до k, поскольку каждый Gi включает только элемент si.
Эта проблема -> Сумма подмножества: та же идея, учитывая, что существует набор одноэлементных групп, суммирующий до k, мы можем выяснить, какие элементы в S нам нужны, чтобы получить желаемое подмножество сумма в S.

Заключение:
Эта задача является NP-сложной, и для нее нет известного полиномиального решения. Поскольку то, что вы ищете, является проблемой оптимизации для проблемы NP-Hard, ваша проблема оптимизации также является NP-Hard. Таким образом, вашим лучшим шансом для получения оптимального решения, вероятно, будет экспоненциальное решение, такое как грубая сила: просто проверьте все возможности и верните лучшее совпадение.

Примечание.

• Из примера 2 кажется, что вам не нужно выбирать элемент из каждой группы, но нужно выбирать не более одного элемента из каждой группы, если это не так - эта проблема все еще NP-Hard, но сокращение будет немного Сильнее.
• все ссылки в моих ответах на Википедию здесь для будущих читателей, поскольку сегодня Википедия отключена. Если вам интересно, вы можете выполнить поиск по этим терминам в Google и просмотреть кешированные страницы.

РЕДАКТИРОВАТЬ: пример экспоненциального решения [псевдокод]:

Обратите внимание, что это не было проверено, но идея, лежащая в основе этого, должна работать: просто проверьте все возможности для первой группы и рекурсивно findBest() с одной группой меньше, так что в конце вы исчерпаете все возможные решения и вернете лучшее из них.

findBest(groups, k):
  if (k < 0): return infinity //stop condition 1
  if (group is empty) return k //stop condition 2
  group <- groups.getFirst()
  min <- infinity
  best <- []
  for each element in group:
     (solValue,minResult) <- findBest(groups-group, k - element) //recursively check for solution, with decreasing number of groups, and modify k
     if (solValue < min):
        min <- solValue
        best <- minResult
        best.append((group,element)) //append the element we added to the solution
  //it is also possible to take no element from this group:
  (solValue,minResult) <- findBest(groups-grou, k - element)
  if (solValue < min):
     min <- solValue
     best <- minResult
  return (minResult,solValue)