这是我的问题。
有一个包含 2N 个元素的未排序数组。所有这些元素都是正整数。问：如何将这个数组分成两个N数组，两个数组的和必须最接近
一个直观的想法是，
- 将此数组排序为 a1< a2 < a3< ...< a2N 和
- 将它们分成两个子数组 a1 a3 a5 ... a(2N-1) 和 [a2,a4,...a2N] ，然后在每个数组中切换两个数字，并继续循环使用我们找到两者之间最小的一个大批。
但是这样一来，我们就不能确定我们找到了最优的。
问问题
223 次
2 回答
5
这是分区问题，而且很难（即 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]
这并不总是给出最佳解决方案，但在大多数情况下它已经足够好了。它还避免了“先行”的偏见。
于 2012-09-12T01:50:20.397 回答
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) 或 Q(i - 1, s - e[i], n - 1)
基本情况说，根本不使用任何元素，子集中的总和和所需数字都必须为零，否则 Q 为假：
Q(0, 0, 0) = true，否则 Q(0, _, _) 为 false。
要得到答案，请计算 Q(2N, k, N), k = 上限(S/2), 上限(S/2)-1, ... 的 DP 表，直到找到真值。
请注意，此问题与子集总和足够接近，使其成为 NP 难题。这意味着真正的多项式时间算法（如您的排序建议）将是最优性的近似值。当然，对于现实目的来说，这可能很好。
于 2012-09-12T01:01:49.310 回答