Как определить, какой промежуточный итог составляет сумму?

Question

мне нужно найти номера в списке, которые составляют определенную сумму:

Sum: 500 

Subtotals: 10 490 20 5 5 

In the end I need: {10 490, 490 5 5} 

Как вы называете этот тип проблем? Существуют ли алгоритмы для ее эффективного решения?

Answer 1

Это Knapsack problem и это NP-полная проблема, то есть нет эффективного алгоритма, известного для него.

Answer 2

1. Это не проблема с рюкзаком.
2. В худшем случае с N промежуточными итогами могут быть решения O (2^N), поэтому любой алгоритм в худшем случае не будет лучше этого (таким образом, проблема не относится к классу NP вообще).

Предположим, что в массиве Subtotals нет неположительных элементов, и любой элемент не превосходит Sum. Мы можем сортировать массив промежуточных итогов, а затем строить массив хвостовых сумм, добавляя 0 к концу. В вашем примере, это будет выглядеть следующим образом:

Subtotals: (490, 20, 10, 5, 5) 
PartialSums: (530, 40, 20, 10, 5, 0) 

Теперь для любого "оставшейся суммы" S, положение I, и "текущий список" L есть проблема E (S, I, L):
E (0, i, L) = (печать L).
E (S, i, L) | (PartialSums [i] < S) = (ничего).
E (S, i, L) = E (S, i + 1, L), E (S-подвычисления [i], j, L || Субтракты [i]), где j - индекс первого элемента из Промежуточные значения, меньшие или равные (S-итоговые значения [i]) или i + 1, в зависимости от того, что больше.
Наша проблема E (Sum, 0, {}).

Конечно, проблема с дубликатами (если в вашем списке было еще 490 номеров, этот алгоритм выдаст 4 решения). Если это не то, что вам нужно, использование массива пар (значение, множественность) может помочь.

P.S. Вы можете также рассмотреть динамическое программирование, если размер проблемы достаточно мал:

1. Начало с набором {0}. Создайте массив множеств, равный массиву промежуточных итогов в размере.
2. Для каждого промежуточного итога создайте новый набор из предыдущего набора, добавив значение промежуточного итога. Удалите все элементы, превышающие сумму. Объедините его с предыдущим набором (это будет по существу множество всех возможных сумм).

3. Если в окончательном наборе нет суммы, то решения нет. В противном случае вы возвращаете решение от Sum до 0, проверяя, содержит ли предыдущий набор значение [value] и [value-subtotal].
   Пример:

   (10, 490, 20, 5, 5)

Наборы:

(0) 
(0, 10) 
(0, 10, 490, 500) 
(0, 10, 20, 30, 490, 500) (510, 520 - discarded) 
(0, 5, 10, 15, 20, 25, 30, 35, 490, 495, 500) 
(0, 5, 10, 15, 20, 25, 30, 35, 40, 490, 495, 500) 

Из последнего набора: [500-5] в предыдущем наборе, [495 -5] в предыдущем наборе, [490-20] не в предыдущем наборе ([490] is), [490-490] равно 0, в результате получается ответ {5, 5, 490}.