如何找出2N数组中最接近的两个子数组之和？考虑找到最优解。

Question

这是我的问题。

有一个由2N个元素组成的未排序数组。所有这些元素都是正整数。 Q：如何将此数组分成两个N个数组，使得两个数组的总和最接近

一种直观的想法是，

1. 将此数组排序为a1<a2 < a3< ...< a2N
2. 将它们分成两个子数组a1 a3 a5 ... a(2N-1)和[a2，a4，...a2N]， 然后在每个数组中交换两个数字，并继续循环，直到找到两个数组之间的最小值。

但是这样做，我们无法确定是否找到了最优解。

- Ivan

---

正如PengOne所述，这个问题是NP完全问题。要找到确切的解决方案，您必须测试所有的C(2n,n)=(2n)!/(n!)²组合...<br> 也许这篇文章可以提供一些帮助：平衡数字分区的完整随时算法，其他参考资料，如应用于平衡数字分区问题的差分方法的性能比率可以指导您实现不同的算法。 - Kwariz

Answer 1

这是 分割问题，它很难（即NP完全问题）。

话虽如此，如果您需要实现这个问题，那么您建议的贪心算法可以做得很好。您可以通过确保一个列表不总是小于另一个列表来稍微改善它，方法是从第一个列表中取1，从第二个列表中取2，再从第一个列表中取2，...以此类推。

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

这种方法并不总能提供最优解，但对大多数情况足够好。它也消除了“先手”的偏见。

- PengOne

---

有关此主题的好文章，请参见：最容易的难题。 - PengOne

Answer 2

你应该查找子集和问题。在你的情况下，你要寻找一个子集和为S/2，其中S是全集的总和。对于整数情况，有一个简单的动态规划算法，这是已知的最佳方法。不幸的是，它是伪多项式时间。这意味着运行时间是元素大小的多项式。这使得它在正常意义下是指数时间，但如果元素不太大，则可以正常工作。

子集和动态规划需要进行一些修改来强制执行恰好N个元素e[i]的要求。让Q(i, s, n)为真当且仅当存在一个子集由1到i中选择的元素总和为s，并且包含恰好n <= i个元素。

然后

Q(i, s, n) = Q(i - 1, s, n) or Q(i - 1, s - e[i], n - 1)

基本情况表示根本不使用任何元素，子集和和所需子集中的元素数量必须都为零，否则Q为false：

Q(0, 0, 0) = true，否则Q(0，_，_)为false。

要得到答案，请计算Q(2N，k，N)的DP表，其中k = ceiling(S/2)，ceiling(S/2)-1，...，直到找到一个true值。

请注意，此问题与子集和问题非常接近，使其成为NP难问题。这意味着真正的多项式时间算法（如您的排序建议）将是最优性的近似。当然，对于实际目的来说，这可能完全可以接受。

- Gene

---

对于 {1,1,1,3}，使用子集和 S/2 得到的结果是 {1,1,1} {3}，但答案应该是 {1,1} {1,3}。我猜这种方法行不通。 - Kwariz

啊，但是子集和动态规划问题有一个微不足道的修改可以解决你的问题。我会进行编辑以向你展示，因为你没有看到它。 - Gene

子集求和问题并不限制两个集合的大小。 - PengOne

我要补充一点，这个问题（以及子集和问题）是NP难的证明。因此，涉及贪心、排序等真正多项式时间的解决方案将是近似解。对于许多应用程序来说，这些近似解可能已经足够好了。 - Gene