algorithm - 恰好 k 个整数的子集和？

Question

根据这些问题 Subset sum problem和 Sum-subset with a fixed subset size我想知道解决子集和问题的一般算法是什么，我们被迫使用恰好 k 个整数，k <= n。

Evgeny Kluev 提到他会选择对 k = 4 使用最优方法，然后对 k- 4 使用蛮力方法，对其余部分使用最优方法。任何人都可以在这里通过结合最佳 k=4 算法的蛮力方法来阐明他的意思？

也许有人知道更好的通用解决方案？

Answer 1

适用原始动态规划算法，稍作扩展 - 除了记住部分和之外，您还需要记住用于求和的整数个数。

原算法中，假设目标和为M还有n整数，你填一个 bool 值 n x M数组 A , 其中A[i,m]为真当且仅当和m可以通过从第一个 i+1 中挑选(任意数量)来实现整数(假设从 0 开始索引)。

你可以把它扩展成三维数组n x M x k ，具有类似的属性 - A[i,m,l]是真的当且仅当，求和m可以通过准确选择l来实现从第一个i+1整数。

假设整数在数组 j[0..n-1] 中:

递归关系非常相似 - 字段 A[0,j[0],1]是真的(你选择 j[0] ，得到总和 j[0] 与 1 int(duh))，A[0,*,*] 中的其他字段在 A[i+1,*,*] 中是假字段和派生字段来自 A[i,*,*]也类似于原来的算法:A[i+1,m,l]如果 A[i,m,l] 为真是真的(如果你可以从第一个 m 整数中选择 i，那么显然你可以从第一个 m 整数中选择 i+1)或者如果 A[i, m - j[i+1], l-1]是真的(如果你选择 j[i+1] 那么你将总和增加 j[i+1] 并将整数的数量增加 1)。

如果k很小，那么显然跳过所有上述部分并迭代 k 的所有组合是有意义的整数并检查它们的总和。 k<=4确实似乎是一个合理的阈值。