代码之家 › 专栏 › 技术社区 › roccapl

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

permutation sum integer algorithm

roccapl · 技术社区 · 13 年前

假设我有一个由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最接近的变体)。

5 回复 | 直到 13 年前

Community Mohan Dere 9 年前

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

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

×××¢× ××¨×§× 13 年前

下面是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

*主要>最小组合[2,4,2,6,9,10,1,7,6,3]
(0,[-7,-10,-2,-4,-2,1,9,6,6,3])

roccapl 13 年前

这是amin k描述的算法的java实现。

它没有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);
}
}

christopher 13 年前

你试过计算差异吗?取第一个数字。找到差值最小的值,然后求和。继续,直到完成。在最坏的情况下,算法的复杂度为O(n^2),这并不完全理想,但这是一个起点

Gianluca Ghettini 13 年前

欢迎来到NP类问题的世界!

你可以通过bruteforce或尝试一种宽松的方法(如单纯形算法)来计算最优解,这将在平均情况复杂度的政治时间内为你带来解