rpl*_*usg 9 algorithm data-structures
我遇到了这个问题,找不到合理的解决方案.如何将未排序的整数数组划分为2个相等大小的子数组,以使子数组之和的差异最小.
例如:给定一个整数数组a [N](未排序),我们希望将数组拆分为a1和a2,其中a1.length == a2.length即N/2和(a1中所有数字的总和 - a2)中所有数字的总和应该是最小的.
为简单起见,我们假设所有数字都是正数,但可能会有重复.
虽然其他人提到这是修改分区问题的情况，但我想更具体地指出，这实际上是两台机器的最小完工时间问题的特殊情况。也就是说，如果您解决两台机器的完工时间问题并获得一个值m，您将获得最小差异2*m - sum(i : i in arr)
正如维基百科文章所述，对于 2 台以上的机器，该问题是 NP 完全问题。但是，在您的情况下，列表调度算法通常提供近似答案，对于给定非递增顺序排序列表的两台机器和三台机器的情况来说，是最优的和多项式时间的。