如何找出哪個小計組成一個總和？

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，我的位置， 「當前列表」 L我們有問題，E（S，I，L）：
E（ 0，i，L）=（打印L）。 （S，i，L）|
E（S，i，L）| （PartialSums [i] < S）=（無）。 （S，i + 1，L），E（S-Subtotals [i]，j，L || Subtotals [i]），其中j是第一元素的索引小計小於或等於（S-小計[i]）或i + 1，以較大者爲準。
我們的問題是E（Sum，0，{}）。

當然，重複出現問題（如果列表中有另外490個數字，此算法將輸出4個解決方案）。如果這不是你所需要的，使用數組對（value，multiplicity）可能會有所幫助。

P.S.如果問題的大小足夠小，您也可以考慮動態編程：

1. 以集合{0}開始。創建大小等於小計數組的數組集合。
2. 對於每個小計，通過添加小計值，從以前的設置創建一個新集。刪除大於Sum的所有元素。將它與前一集合並（它將基本上是所有可能的總和）。

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]是），[490-490]爲0，結果爲{5,5,490}。