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 的变体）。

4

5 回答 5

1

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

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

于 2013-03-02T14:29:06.083 回答
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])

于 2013-03-02T20:31:46.383 回答
1

这是 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);
}
}
于 2013-03-03T13:51:44.307 回答
0

您是否尝试过计算差异？即：取第一个数字。找出差值最小的值，然后求和。继续直到完成。在最坏的情况下，算法是 O(n^2) 复杂度，这不是完全可取的，但它是一个起点

于 2013-03-02T13:54:21.297 回答
0

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

您可以通过蛮力或尝试一种轻松的方法（如单纯形算法）计算最佳解决方案，这将在多项式时间内为您提供平均情况复杂度的解决方案

于 2013-03-02T14:08:56.053 回答