algorithm - 给定 N 个整数的绝对值，找到 N/2 个负值和 N/2 个正值的组合，其总和最接近 0

Question

假设我有一个包含 10 个数字的数组，其绝对值范围可以从 1 到 10。值可以重复。这方面的一个例子可能是

{2, 4, 2, 6, 9, 10, 1, 7, 6, 3}. 

我们可以为这些数字中的每一个分配一个正号或负号，但是在每个组合中应该始终有 5 个负数和 5 个正数，例如

{-2, -4, 2, -6, 9, 10, 1, 7, -6, -3}
{2, -4, -2, 6, -9, 10, -1, 7, -6, 3}

是遵循此规则的可能排列。

我想在给定集合的半正值和半负值的所有可能排列中，找到值最接近 0 的最小正或负和。

有什么建议吗？我觉得这个问题在计算上非常密集，我不确定是否有一种解决方案不是蛮力解决方案(例如枚举所有排列，然后应用最接近的 3Sum 的变体)。

Answer 1

首先对数组进行排序，然后将最大的数放入负数组，将第二大的数放入正数组。将最大的数字设置为正组，直到它们的总和大于零。现在设置另一个负数。重复直到设置 5 个负数。这就是贪心算法。似乎你的问题是 np-complete，它看起来像 AST 问题但是，你的问题的大小限制为 10，所以你可以通过强力搜索来解决它，你只需要检查 C(10,5)<10^5 可能性对于今天的个人电脑来说，这个数字很小。

此外，如果能够选择不同大小的集合，则您的问题与可以在伪多项式时间内解决的子集和问题相同，请参阅:1 , 2 .