algorithm - 将一个整数数组分成两个大小相等的子数组？

Question

我遇到了这个问题，找不到合理的解决方案。如何将未排序的整数数组划分为 2 个大小相等的子数组，以使子数组和之间的差异最小。

例如：给定一个整数数组 a[N]（未排序），我们希望将数组拆分为 a1 和 a2，其中 a1.length == a2.length 即 N/2 和（a1 中所有数字的总和 - a2) 中所有数字的总和应该是最小值。

为简单起见，我们假设所有数字都是正数，但可能会有重复。

Answer 1

虽然其他人提到这是修改分区问题的一个案例，但我想更具体地说，它实际上是两台机器的最小制造时间问题的一个特例。即，如果您解决两机制造时间问题并获得一个值m，您将获得最小差异2*m - sum(i : i in arr)

正如维基百科文章所述，对于超过 2 台机器，问题是 NP 完全的。但是，在您的情况下，通常提供近似答案的List 调度算法对于两台机器和三台机器的情况是最优的和多项式时间，给定一个非递增顺序的排序列表。

有关此算法的详细信息以及更多理论结果，请参见此处。