将一个整数列表分割以最小化它们之和的差

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)).abs尽可能小，其中S = [sum(g1), sum(g2), ... sum(gk)]是总和的列表。

- pathikrit

---

修改后的问题（泛化）完全改变了事情。k-分区是强NP完全问题，目前没有已知的伪多项式解决方案。 - amit

Answer 1

一种朴素、简单而仍然是伪多项式的解决方案是使用现有的子集和解决方案，并重复执行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)

构建矩阵时，上述实际上为您创建了每一行，其值均低于初始值x，如果输入sum（array）/2-基本上是所有值。

生成DP矩阵后，只需找到最大值x，使得f（x，n）= true，这就是您可以获得的最佳分区。

在这种情况下，复杂度为O（Wn）

- amit

---

但这只给了我x，如果我真的想知道分区是什么怎么办？ - pathikrit

@wrick，获取实际分区相当容易，只需从给定的 x 开始跟随表格并检查每个点上做出了哪些“决策”。我曾在以下主题中为类似的背包算法解释过：如何使用背包算法找到哪些元素在袋子里（而不仅仅是袋子的价值）？。尝试遵循那个方法，如果有任何困难，请告诉我。 - amit

@wrick 对于表格中的每个 1，要记住它是如何出现的。 - Niklas B.

Answer 2

你可以将其表述为0/1整数线性规划优化问题。设wi为第i个数字，xi为一个0/1变量，表示wi是否在第一组中。然后，您要最小化sum(xi wi) - sum((1 - xi) wi)，并满足以下条件：

sum(xi wi) >= sum((1 - xi) wi)

同时还要满足所有xi都是0或1。已经有很多研究致力于优化0/1线性规划求解器。对于总和W较大的情况，这可能比O(W n)伪多项式时间算法更好，因为W因素令人生畏。

- user2566092

Answer 3

我的第一个想法是：

1. 对整数列表进行排序
2. 创建两个空列表 A 和 B
3. 在从最大整数到最小整数的迭代过程中...将下一个整数添加到当前总和最小的列表中。

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

- Ivan

---

这是一个非最优贪心解决子集和问题的方法。原帖作者澄清了他正在寻找优化的解决方案，并提供了学习最优解决方案的链接。 - amit

我看到“pseudo”，想到了“伪最优”（不是伪多项式）。 - Ivan

假设你有一个包含n个数字的序列，前n-1个数字的值为k，第n个数字的值为k(n-1)。那么你的解决方案将会相当低效。 - ealfonso