这个子集求和问题的变体是否更容易解决？

Question

我遇到了与 子集和问题 相关的问题，想知道这三个不同点是否能使它更容易解决，即在合理的时间内解决。

给定一个值V、一个集合大小L和一个序列[1,N]S，有多少个S的大小为L的子集的和小于V？

这与子集和问题不同的三个方面是：

1. 我关心有多少子集小于给定的值，而不是有多少个相等。
2. 子集大小是固定的。
3. 我关心有多少个子集的和小于V，而不仅仅是是否存在任何子集的和小于V。

是否有任何合理有效的算法来解决这个问题？

编辑： 显然，可以使用组合生成算法在O(N choose L)中完成。我真正感兴趣的是聪明的技巧，以显著加快它的速度。

- dsimcha

---

这不就是有点变化的背包问题吗？不过我可能错了。 - Lasse V. Karlsen

Answer 1

你的问题的决策版本仍然是NP完全问题。思路是，如果我们能够解决你的问题，那么（对于每个子集大小，例如）我们可以询问有多少个集合总和小于V，有多少个集合总和小于V-1，这两个数的差告诉我们是否存在子集总和恰好为V - 因此我们可以解决子集和问题。[这不是一个完整的证明，因为它是一个图灵归约，而不是一个一对多归约。]

然而，有一个简单的动态规划解决方案，运行时间为O(nLV)。[这并不意味着P = NP，因为V可能是输入大小的指数级：用n位表示值可以达到2 ⁿ 。但是假设你的V不是指数级别的，那么这不是问题。]

让num[v][k][i]表示S的前i个元素中大小为k的子集的总和为v的数量。您可以按以下方式计算它们（对于每个i）：

    num[0][0][i] = 1
    for v = 1 to V:
        for k = 1 to L:
            num[v][k][i] = num[v][k][i-1] + num[v-S[i]][k-1][i-1]

其中S[i]是您序列中的第i个元素。(任何大小为k且总和为v的集合都不使用S [i]，因此在num [v] [k] [i-1]中计算，或者使用S [i]，这意味着子集的其余部分具有k-1个元素，在序列中仅使用前i-1个数字，并且总和为v-S [i]。)最后，对于每个小于V的v，计算num [v] [L] [| S |]，这就是您的答案。

此外，如果您小心地操作（向下运行每个i的循环等），则可以省略第三个下标；我只是为了清晰起见而包含它。

- ShreevatsaR

Answer 2

我没有准备好提供证明，但这似乎可以采用动态规划方案：制表列出大小为2的子集列表，使用它们计算大小为3的子集等等，这样您只需要检查一小部分前景即可。

- Charlie Martin

Answer 3

子集和问题的动态规划解决方案生成一个包含此答案的表格（即一个布尔表，大小为V乘N，其中V是元素的最大数量，N是满足约束条件的集合中可以有的最大项数；每个布尔值为真，如果<= N个元素总和<= V）。因此，如果N * V对您来说不太大，则存在一种可接受的快速算法。子集和解决方案只是该表中最高的集合元素，其元素数量<= N/2。

- Graham Toal

Answer 4

我想到的一个优化方法是这样的：对序列进行排序（如果尚未排序）。从开头选择前L-1个项目，然后选择最后一个项目，使其成为可能的最大值（序列中下一个最大值会导致总和过大）。丢弃序列的其余部分，因为这些项目永远不可能成为有效子集的一部分。

之后，我猜又要进行全面搜索。但是再说一遍，可能还有其他的优化方法。

- Vilx-

Answer 5

如果只有正整数，您可以进行验证步骤（如果需要的话）;

取集合中L-1个最小整数的总和。 如果这是一个总和X，则n-X必须低于最大元素，如果问题假定有解决方案。 经过思考，您可以用这种方式消除其他L...

- InCog

Answer 6

也许动态规划公式可以适用于FPTAS或PTAS。

- anonymous

Answer 7

嗯，首先，由于您指定了size=L，即使您无法想出任何聪明的方法，只是使用暴力算法，在最坏情况下您将有(N choose L)个单独的和，因此它比n^^L（好吧，L+1，因为您将对每个子集求和）要好一些。

- Steve B.

Answer 8

这似乎是一个n选k问题类别。在Skiena的算法设计手册中，生成n个元素的k子集已经有所涉及，并且该书建议按字典顺序枚举相关子集（例如递归）。然后对每个子集进行求和和比较。

如果您有一个排序的集合，您可以从解空间中剪枝不可能的解决方案。

- JasonTrue