整数指定N绝对值找到N / 2个负和N / 2个正值，其总和的组合最接近0 [英] given N absolute values of integers find the combination of N/2 negative and N/2 positive values whose sum is closest to 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).

推荐答案

首先排序数组，然后把最大数量为阴性对照组，把第二大成阳性组。 设置一个最大数量为阳性对照组，直到它们的总和大于零。 现在设置等负面number.repeat它，直到你设置5负。这是贪心算法。 看来你的问题是NP完全问题，它看起来像AST问题，但你的问题的大小限制为10，这样你就可以通过蛮力搜索解决它，你只需要检查C（10,5）小于10 ^ 5可能性，这个数字是小，今天的电脑。

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.

这篇关于整数指定N绝对值找到N / 2个负和N / 2个正值，其总和的组合最接近0的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！