algorithm - 如何找出哪个小计构成总和？

Question

我需要在列表中查找数字，这些数字构成了特定的总数：

Sum: 500

Subtotals: 10 490 20 5 5

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

你怎么称呼这种类型的问题？有没有算法可以有效地解决它？

Answer 1

这是背包问题，它是一个 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) = (print L)。
E(S, i, L) | (PartialSums[i] < S) = (什么都没有)。
E(S, i, L) = E(S, i+1, L), E(S-Subtotals[i], j, L||Subtotals[i])，其中 j 是小计的第一个元素的索引 lesser大于或等于 (S-Subtotals[i]) 或 i+1，以较大者为准。
我们的问题是 E(Sum, 0, {})。

当然，重复存在问题（如果您的列表中还有另外 490 个数字，此算法将输出 4 个解决方案）。如果这不是您需要的，使用对数组（值，多重性）可能会有所帮助。

PS如果问题的大小足够小，您也可以考虑动态编程：

1. 从集合 {0} 开始。创建大小等于小计数组的集合数组。
2. 对于每个小计，通过添加小计值从以前的集合创建一个新集合。删除所有大于 Sum 的元素。将它与之前的集合合并（它本质上是所有可能总和的集合）。

3. 如果最终集合中没有 Sum，则没有解决方案。否则，您将解决方案从 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}。