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

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

3 голосов
/ 18 января 2012

У меня есть несколько групп данных, таких как

Group1 2,3,5,10,15Группа2 4,6,23,15,12Группа 3 23,34,12,1,5

мне нужна лучшая сумма (пример суммы (g1 + g2 + g3) <= 25) из этих 3 групп, таких как </p>

1-й (g1) 5 + (g2) 15 + (g3) +5 = 25 (лучшая комбинация)

Теперь для следующего набора комбинаций нет необходимости использовать вышеуказанные значения из каждой соответствующей группы

Group1 2,3, 5 ,10,15Группа2 4,6,23 15 12Группа 3 23,34,12,1, 5

2-й (g1) 2 + (g2) 23 = 25 (лучшая комбинация)

Group1 2 , 3, 5 , 10,15Группа2 4,6, 23 , 15 , 12Группа 3 23,34,12,1, 5

3-й (g1) 15 + (g2) 6 + (g3) + 1 = 22 (лучшая комбинация)

Надеюсь, это может быть немного сложно.Но я мог бы получить лучшее решение для этой проблемы.

Спасибо

Ответы [ 2 ]

4 голосов
/ 18 января 2012

Это NP-Hard проблема.

Существует сокращение от поднабора суммы
Проблема поднабора суммы :для заданного мультимножества S и числа k: вернуть true, если и только если есть подмножество S' из S, которое в сумме в точности равно k.

Сокращение:
Учитывая экземпляр проблемы суммы подмножеств в форме (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-Hard, и для нее нет известного решения для полинома.Поскольку вы ищете проблему оптимизации для задачи 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)
0 голосов
/ 20 января 2012

Задача суммы подмножества имеет подход псевдополиномиального динамического программирования. Мы можем сопоставить ее с этой проблемой вариации со сложностью O(S*N) и O(S) пробел, где S - максимальная сумма (25 в вашем примере), а N - общее количество элементов во всех группах.

Эта сложность не зависит от общего количества групп, поэтому лучше подходит, если O(N^G) решение с использованием грубой силы не будет сходиться для высоких значений G>=10. Но обратите внимание, что этот алгоритм не будет работать для S>=biginteger.

Короче говоря, рекурсивное решение DP выглядит следующим образом: 

Sol(grp_i, S) = True      if(grp_i==1 && grp_i dataset has element S) // base case
              = True      if(Sol(grp_i-1, S)==True OR
                             there exists element 'e' in grp_i dataset
                             such that Sol(grp_i-1, S-e)==True)
              = False     otherwise

Как только мы выясним, является ли набор данных разрешимым, мы можем вернуться к решению.

Программа Python ниже: 

def bestsum(data, maxsum):
  res = [0]*(maxsum+1)
  res[0] = []  # base case
  for group in data:
    new_res = list(res) # copy res
    for ele in group:
      for i in range(maxsum-ele+1):
        if res[i] != 0:
          new_res[i+ele] = list(res[i])
          new_res[i+ele].append(ele)
    res = new_res
  for i in range(maxsum, 0, -1):
    if res[i] != 0:
      return res[i]
      break
  return []

print bestsum( [[2,3,5,10,15], [4,6,23,15,12], [23,34,12,1,5]], 25)
print bestsum( [[2,3,10,15],   [4,6,23,12],    [23,34,12,1]],   25)
print bestsum( [[3,10,15],     [4,6,12],       [23,34,12,1]],   25)

Выход: 

~$ python2 subsetsum.py
[5, 15, 5]
[2, 23]
[12, 12]
...