Bob*_*r02 3 algorithm subset-sum
根据这些问题子集和问题 和具有固定子集大小的Sum子集我想知道解决子集和问题的一般算法是什么,我们被迫使用完全k个整数,k <= n.
Evgeny Kluev提到他将使用k = 4的最优值,之后使用蛮力逼近k-4并且其余为最佳.任何人都可以通过蛮力方法结合最佳k = 4算法来体现他的意思吗？
也许有人知道更好的通用解决方案？
最初的动态编程算法适用,只需稍加扩展 - 除了记住部分和之外,还需要记住用于获得总和的int数.
在原始算法中,假设目标总和是M并且存在n整数,则填充布尔nx M数组A,A[i,m]如果m可以通过从第一个i+1整数中拾取(任意数量)来实现求和(假设从0开始索引),则为真.
您可以将它扩展为具有类似属性的三维数组nx Mx k- 如果A[i,m,l]是if,m则可以通过l从第一个i+1整数中精确选取来实现求和.
假设int是数组j[0..n-1]:
递归关系非常相似 - 字段A[0,j[0],1] 为真(你选择j[0],得到j[0]1个int(duh)的和),其他字段A[0,*,*]为false,而A[i+1,*,*]from中的字段A[i,*,*]也与原始算法类似:A[i+1,m,l]如果A[i,m,l]为真则为true(如果你可以m从第一个i整数中选择,然后显然你可以m从第一个i+1整数中选择)或者如果A[i, m - j[i+1], l-1]是真的(如果你选择j[i+1]那么你增加总和,j[i+1]并将整数个数增加1).
如果k很小,那么显然跳过上述所有部分并迭代所有的k整数组合并检查它们的总和是有意义的.k<=4确实看起来像是一个明智的门槛.