给定N个整数的绝对值，找到N/2个负值和N/2个正值的组合，使它们的和最接近于0。

Question

给定N个整数的绝对值，找到N/2个负值和N/2个正值的组合，使它们的和最接近于0。

3

假设我有一个包含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 closest的变体）。

- roccapl

你尝试过计算差异吗？例如：取第一个数字，找到差异最小的值并求和。继续直到完成。在最坏情况下，该算法的复杂度为O(n^2)，这并不是理想的，但它是一个起点。 - christopher

我会将其发布为潜在答案。如果这有帮助，您可以将其标记为正确。 - christopher

5个回答

1

这里是一个使用 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

*Main> minCombi [2, 4, 2, 6, 9, 10, 1, 7, 6, 3]
(0,[-7,-10,-2,-4,-2,1,9,6,6,3])

*主函数> minCombi [2, 4, 2, 6, 9, 10, 1, 7, 6, 3]
(0,[-7,-10,-2,-4,-2,1,9,6,6,3])

- גלעד ברקן

谢谢，我对 Haskell 语言一无所知，但我会深入了解它... - roccapl

1

这是一个Java实现的算法，由amin 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);
}
}

- roccapl

0

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

- christopher

这是一种贪婪的方法，不适合解决这个问题，你会得到一个局部最小值（次优解）。 - Gianluca Ghettini

我试图在纸上按照你的算法进行，但我不确定我完全理解了它。找到下一个差异最小的数字的最佳方法是在迭代之前按升序对数组进行排序。那么我应该加什么？数字？还是差异？ - roccapl

@G_G，也许你可以提供一个更高效的解决方案？等待G_G。在你看到可能更好的解决方案之前，没有必要浪费时间看我的。 - christopher

0

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

你可以通过蛮力计算或者尝试一种放松的方法（比如单纯形算法），在平均情况下以多项式时间复杂度找到最优解。

- Gianluca Ghettini

我猜你的意思是NP完全问题（NP-complete）。NP包含P。如果NP != P，则NP完全问题指的是不在P中的问题。如果你想说它是NP完全问题，你应该给出合理的解释。 - Bernhard Barker

没错，NP类问题也称为NP完全问题。这个问题是著名的背包问题的一个变体。 - Gianluca Ghettini

NP类问题（http://en.wikipedia.org/wiki/NP_(complexity)）并不等同于NP完全问题（http://en.wikipedia.org/wiki/NP-complete）（请看右侧的图片）。它可能是背包问题的一个变体，但并不明确，因此您应该说明它如何归约到背包问题。 - Bernhard Barker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amin k · Accepted Answer

首先对数组进行排序，然后将最大的数放入负数组中，将第二大的数放入正数组中。将一个最大的数放入正数组中，直到它们的总和超过零。现在设置另一个负数。重复此步骤，直到设置5个负数。这是一种贪婪算法。看起来你的问题是np完全的，它看起来像AST问题，但是你的问题规模只有10，所以你可以通过暴力搜索来解决它，你只需要检查C（10,5）<10^5个可能性，这个数字对于今天的PC来说很小。此外，如果能够选择不同大小的集合，那么你的问题就与子集和问题相同，可以在伪多项式时间内解决。请参见：1，2。