给定 N 个整数的绝对值，求 N/2 个负值和 N/2 个正值的总和最接近 0 的组合

本文介绍了给定 N 个整数的绝对值，求 N/2 个负值和 N/2 个正值的总和最接近 0 的组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

Let's say that I have an array of 10 numbers whose absolute value range can go from 1 to 10. Values can be repeated. An example of this could be

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

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

To each of these numbers we can assign a positive or negative sign, but there should be always 5 negative and 5 positive numbers in each combination, for example

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

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

are possible permutation that follow this rule.

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

I would like to find, in all the possible permutations of half-positive and half-negative values of the given set, the minimum positive or negative sum whose value is closest to 0.

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

Any suggestions? I feel that the problem is computationally very intensive and I'm not sure there is a solution that is not a brute force one (for example enumerating all the permutations and then applying a variation of the 3Sum closest).

推荐答案

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

First sort the array, then put the biggest number into negative group and put Second-biggest into positive group. set a biggest number into positive group until sum of them is more than zero. Now set an other negative number.repeat it until you set 5 negative. This is greedy algorithm. Seems your problem is np-complete, it looks like AST problem but, size of your problem is limited to 10, so you can solve it by brute force search, you just have to check C(10,5)<10^5 possibilities and this number is small for today PCs.

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

Also if was able to choose different size of sets, your problem was same as subset sum problem which can be solve in pseudo-polynomial time See it :1 , 2.