整数指定N绝对值找到N / 2负和N / 2正值其总和的组合最接近0(given N absolut

比方说，我有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负现在设置的其他负面number.repeat它。这是贪心算法。看来你的问题是NP完全问题，它看起来像AST问题，但是，你的问题的大小限制为10，这样你就可以通过蛮力搜索解决它，你只需要检查C（10,5）<10 ^ 5点的可能性而这个数字是小为今天的PC。

此外，如果能够选择的套不同大小，你的问题是一样的子集和问题可以在伪多项式时间内解决看它： 1 ， 2 。

Answer 2:

下面是Haskell中，列出所有可能的126个组合进行比较的例子：

import Data.List
import Data.Ord

{-code by Will Ness-}
divide :: [a] -> [([a], [a])]
divide [] = [([],[])]
divide (x:xs) = go ([x],[],xs,1,length xs) where
  go (a,b,[],i,j) = [(a,b)]
  go (a,b, s@(x:xs),i,j) 
     | i>=j = [(a,b++s)]
     | i>0  = go (x:a, b, xs, i+1, j-1) ++ go (a, x:b, xs, i-1, j-1)
     | i==0 = go (x:a, b, xs,   1, j-1) ++ go (x:b, a, xs,   1, j-1)  

{-code by groovy-}       
minCombi list = 
  let groups = map (\x -> map (negate) (fst x) ++ snd x) (divide list)
      sums = zip (map (abs . sum) groups) groups
  in minimumBy (comparing fst) sums

*主要> minCombi [2，4,2，6，9，10，1，7,6，3]
（0，[ - 7，-10，-2，-4，-2,1,9,6,6,3]）

Answer 3:

这是一个Java实现由阿明k中描述的算法的。

它不太酷比Haskell的实现，我没有正式的证据，它的作品在任何情况下，但它似乎是工作。

import java.util.Arrays;
import java.util.Random;

public class TestPermutations {

int[] values = new int[10];
int[] positives = new int[5];
int[] negatives = new int[5];

public static void main(String... args) {
    new TestPermutations();
}

public TestPermutations() {
    Random ra = new Random();
    System.out.println("generating sequence...");
    for (int i = 0; i < 10; i++) {
        values[i] = (ra.nextInt(10) + 1);
        System.out.print(values[i] + " ");
    }
    Arrays.sort(values);

    int sum = 0;
    int positiveIndex = 0;
    int negativeIndex = 0;
    for (int i = values.length - 1; i >= 0; i--) {
        if (i == values.length - 1) {
            negatives[negativeIndex] = - values[i];
            negativeIndex++;
            sum -= values[i];
        }
        else {
            if (sum <= 0) {
                if (positiveIndex < 5) {
                    positives[positiveIndex] = values[i];
                    positiveIndex++;
                    sum += values[i];
                }
                else {
                    negatives[negativeIndex] = - values[i];
                    negativeIndex++;
                    sum -= values[i];
                }
            }
            else {
                if (negativeIndex < 5) {
                    negatives[negativeIndex] = - values[i];
                    negativeIndex++;
                    sum -= values[i];
                }
                else {
                    positives[positiveIndex] = values[i];
                    positiveIndex++;
                    sum += values[i];
                }
            }
        }
    }

    System.out.print("\npositives ");
    for (int pos : positives) {
        System.out.print(pos + " ");
    }
    System.out.print("\nnegatives ");
    for (int neg : negatives) {
        System.out.print(neg + " ");
    }
    System.out.println("\nsum closest to 0: " + sum);
}
}