如何计算出2N阵列中两个子阵列的最近和？考虑找到最佳的一个

Question

这是我的问题.

有一个带有2N元素的未排序数组.所有这些元素都是正整数.问:如何将此数组拆分为两个N数组,并且两个数组的总和必须彼此最接近

一个直观的想法是,

1. 将此数组排序为a1 <a2 <a3 <... <a2N和
2. 将它们分成两个子阵列a1 a3 a5 ... a(2N-1)和[a2,a4,... a2N],然后在每个aray中打开两个数字,并保持循环util我们找到两者之间的最小值阵列.

但通过这种方式,我们无法确定我们是否找到了最佳方案.

Answer 1

这是分区问题,而且很难(即NP完全).

也就是说,如果你需要实现这个,那么你建议的贪婪算法做得不错.你可以通过确保一个列表并不总是小于另一个列表,从第一个中取1,从第二个中取2,从第一个中取2,......,从第二个取1,可以做得更好一点:

A = [a1, a4, a5, a8, a9, ..., a(n-2), a(n-1)]
B = [a2, a3, a6, a7, ..., a(n-4), a(n-3), an]

这并不总能提供最佳解决方案,但对大多数情况来说它都做得很好.它也避免了"先走"的偏见.