我有一个与子集和问题有关的问题，我想知道这些差异是否使它更容易，即可以在合理的时间内解决。
给定一个值 V、一个集合大小 L 和一个数字序列 [1,N] S，S 中有多少个大小为 L 的子集总和小于 V？
这在三个方面不同于子集和问题：
有没有合理有效的算法来解决这个问题？
编辑：显然，这可以使用组合生成算法在 O(N choose L) 中完成。我真正感兴趣的是可以显着加快速度的巧妙技巧。
（决策版本）您的问题仍然是 NP 完全的。这个想法是，如果我们可以解决您的问题，那么（例如，对于每个子集大小）我们可以询问有多少集合总和小于 V，有多少集合总和小于 V-1，这两个数字的差将告诉我们是否是子集的总和正好为 V——因此我们可以解决子集和问题。[这不是一个完整的证明，因为它是图灵归约，而不是多一归约。]
但是，有一个简单的动态规划解决方案可以在 O(nLV) 时间内运行。[这不能证明 P=NP 的原因是 V 可以是输入大小的指数：使用 n 位，您可以表示高达 2 n的值。但假设你的 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 个元素。（总和为 v 的任何大小 k 集合要么不使用 S[i]，所以它被计入 num[v][k][i-1]，或者它使用 S[i]，这意味着其余的该子集有 k-1 个元素，仅使用序列中的前 i-1 个数字，并求和为 vS[i]。）最后，为每个小于 V 的 v 计数 num[v][L][|S|] ; 这就是你的答案。
此外，如果您仔细操作，您可以省略第三个下标（为每个 i 向下运行循环，等等）；我只是为了清楚起见才包括它。
我不准备提供证明，但这听起来可能适合动态编程方案：将大小为 2 的子集列表制成表格，将它们用于计算机大小为 3 的子集，等等，这样你只需要检查一个前景的小集合。
想到的一种优化是：订购您的序列（如果不是这样的话）。从开头选择前 L-1 个项目，然后选择最后一个项目，使其成为可能的最大值（序列中的下一个最大值会给出一个太大的总和）。丢弃序列的其余部分，因为这些项目无论如何都不能成为有效子集的一部分。
在那之后，我想它又是完整的搜索。但话又说回来，也可能有其他优化。
子集和问题的动态规划解决方案生成一个包含该答案的表（即 V 乘 N 的布尔表，其中 V 是最大元素数，N 是满足约束；如果 <=N 个元素总和为 <=V，则每个布尔值都为真。因此，如果 N * V 对您来说不是太大，则存在可接受的快速算法。子集和解就是该表中元素数 <= N/2 的最高集合元素。
如果它只是正整数，你可以根据需要做一个验证步骤；
取集合中 L-1 个最小整数的总和。如果这是和 X，那么如果问题应该有解决方案，则 nX 必须低于最大元素。想一想，你可以这样消除其他L...
好吧，一方面，因为您指定 size=L 那么即使您想不出任何聪明的方法而只是使用蛮力，在最坏的情况下您将拥有（N选择L）单独的总和，所以它会更好一些比 n^^L （嗯，L+1，因为你会对每个子集求和）。
这听起来像是一个 n 选择 k 类别的问题。Skiena 的算法设计手册中介绍了生成 n 的 k 子集，并且该书建议按字典顺序（例如递归）枚举相关子集。然后对每个子集进行求和和比较。
如果您有一个排序集，您大概可以从解决方案空间中剪除不可能的解决方案。
也许动态规划公式适用于 FPTAS 的 PTAS。