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

Question

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

algorithmdata-structures

9

我看到这个问题，但找不到一个合理的解决方案。如何将未排序的整数数组分成两个大小相等的子数组，使得子数组之间的差异最小。

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

为了简单起见，假设所有数字都是正数，但可能存在重复。

- rplusg

原始数组已排序？LOL - जलजनक

@SparKot 好的，我不知道那个细节。我们假设是未排序的。 - rplusg

3

看起来你遇到了分割问题。虽然不是完全相同的问题，但之前的一个问题的答案可能同样适用于此处。 - Jerry Coffin

有人可以为Differencing Algo编写代码吗？ - जलजनक

1

正如@JerryCoffin所说，这是一个带有简单修改的“分区问题”。我可以补充说明修改的内容在于a1.length == a2.length，可以通过从最大数组中获取最小数字并将它们放入另一个数组中，直到满足条件为止来解决。 - mamdouh alramadan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andrew Mao · Accepted Answer

虽然其他人已经提到这是一个带修改的划分问题，但更具体地说，它实际上是两台机器的最小完工时间问题的一个特殊情况。即，如果您解决了两台机器的完工时间问题并获得一个值m，则您将获得最小差异2*m-sum(i:i in arr) 正如维基百科文章所述，对于超过2台机器，该问题是NP完全问题。然而，在您的情况下，列表调度算法在非递增排序的情况下为两台和三台机器提供了最优且多项式时间的近似答案。

如需了解此算法的详细信息和更多理论结果，请参见此处。