将整数列表分区，以最小化它们总和的差异

Question

给定一个整数列表l，我如何将其划分为两个列表a和b，使得d（a，b）=abs（sum（a）-sum（b））最小。我知道这个问题是NP完全的，所以我正在寻找一个伪多项式时间算法，即O（c*n）其中c=sum（l map abs）。我看了维基百科，但是算法是把它分成精确的两半，这是我要找的一个特例...

编辑：为了澄清，我正在寻找确切的分区a和b，而不仅仅是产生的最小差异d（a，b）

概括地说，什么是伪多项式时间算法，将一个n数字列表划分成k组g1，g2... gk，使得（max（S）-min（S））。absS=[和（g1），和（g2），...和（gk）]

Answer 1

我的第一个想法是：

1. 整数排序列表

当然，这并不能保证给你最好的结果，但是你可以用列表中最大整数的大小来限制它给你的结果

Answer 2

你可以将其表述为0/1整数线性规划优化问题。设Wi为第i个数，并设席是0/1个变量，表示Wi是否在第一个集合中。然后你想最小化sum（xi-wi）-sum（（1-xi）wi）以

苏姆（xi wi）

而且所有的席都是0或1。有很多关于优化0/1线性规划求解器的研究。对于大和W，这可能是对O（Wn）伪多项式时间算法的改进，因为W因子很可怕。

Answer 3

一个简单的、平凡的、仍然是伪多项式的解决方案是使用现有的解决方案来子集sum，并将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）