给定一个整数列表 l，我如何将它分成 2 个列表 a 和 b 使得 d(a ,b) = abs(sum(a) - sum(b)) 是最小值。我知道这个问题是 NP 完全的，所以我正在寻找一个伪多项式时间算法，即 O(c*n) 其中 c = sum(l map abs) .我看了Wikipedia但是那里的算法是将它精确地分成两半，这是我正在寻找的一个特例......
编辑:
为了澄清，我正在寻找确切的分区 a 和 b 而不仅仅是由此产生的最小差异 d(a, b)
概括地说，将 n 数字列表划分为 k 组的伪多项式时间算法是什么 g1, g2 ...gk 使得 (max(S) - min(S)).abs 尽可能小，其中 S = [sum(g1), sum(g2), ... sum (gk)]
最佳答案
一个天真、简单且仍然是伪多项式的解决方案是使用现有的解决方案进行子集求和，并重复 sum(array)/2 到 0(并返回找到的第一个).
此解决方案的复杂度为 O(W^2*n)，其中 W 是数组的总和。
伪代码:
for cand from sum(array)/2 to 0 descending:
subset <- subsetSumSolver(array,cand)
if subset != null:
return subset
上面将返回小于/等于sum(array)/2的最大子集，另一部分是返回子集的补集。
但是，子集和的动态规划应该足够了。
回想一下公式是:
f(0,i) = true
f(x,0) = false | x != 0
f(x,i) = f(x-arr[i],i-1) OR f(x,i-1)
在构建矩阵时，如果您输入 sum(array)/2 - 它基本上是所有值，则上面的内容实际上会为您创建每行，其值低于初始 x。
生成 DP 矩阵后，只需找到 x 的最大值，使 f(x,n)=true，这是您可以进行的最佳划分得到。
这种情况下的复杂度是O(Wn)
关于algorithm - 对整数列表进行分区以最小化它们的和的差异，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23160454/