从这些问题子集和问题 和具有固定子集大小的和子集之后，我想知道解决子集和问题的一般算法是什么，我们被迫使用完全 k 个整数，k <= n。
Evgeny Kluev 提到他会选择对 k = 4 使用最优方法，然后对 k-4 使用蛮力方法，对其余部分使用最优方法。任何人都可以在这里通过蛮力方法结合最佳 k=4 算法来阐明他的意思吗？
也许有人知道更好的通用解决方案？
问问题
3884 次
1 回答
6
原始的动态规划算法适用，稍作扩展 - 除了记住部分和外，您还需要记住用于获得总和的整数数量。
在原始算法中，假设目标总和是M并且有n整数，则填充一个布尔nxM数组A，如果可以通过从第一个整数中选取（任意数量）来实现A[i,m]总和（假设从 0 开始索引），则为真。mi+1
您可以将其扩展为具有相似属性的三维数组nx Mx k——当且仅当且仅当且可通过从第一个整数中选取来实现A[i,m,l]总和时。mli+1
假设整数在数组中j[0..n-1]：
递归关系非常相似 - 字段A[0,j[0],1] 为真（您选择，用 1 int (duh)j[0]获取总和），其他字段为假，从 from中派生字段也类似于原始算法：如果为真则为真（如果你可以从第一个整数中选择，那么显然你可以从第一个整数中选择）或者如果为真（如果你选择，那么你将总和增加，整数的数量增加 1）。j[0]A[0,*,*]A[i+1,*,*]A[i,*,*]A[i+1,m,l]A[i,m,l]mimi+1A[i, m - j[i+1], l-1]j[i+1]j[i+1]
如果k很小，那么显然跳过所有上述部分并仅迭代所有k整数组合并检查它们的总和是有意义的。k<=4确实似乎是一个合理的门槛。
于 2012-03-23T14:08:12.340 回答