3

絶対値の範囲が 1 から 10 までの 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

これは、aminkによって記述されたアルゴリズムの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 に答える
1

126 の可能な組み合わせすべてを一覧表示して比較する Haskell の例を次に示します。

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

最初に配列をソートし、次に最大数を負のグループに入れ、2 番目に大きいものを正のグループに入れます。それらの合計がゼロより大きくなるまで、正のグループに最大の数を設定します。次に、別の負の数を設定します。負の 5 を設定するまで繰り返します。これは貪欲なアルゴリズムです。あなたの問題はnp-completeのようです.ASTの問題のように見えますが、問題のサイズは10に制限されているため、ブルートフォース検索で解決できます.C(10,5)<10^5の可能性を確認するだけです.この数は、今日の PC では小さいものです。

また、異なるサイズのセットを選択できた場合、問題は疑似多項式時間で解くことができる部分集合和の問題と同じでした : 1 , 2 .

于 2013-03-02T14:29:06.083 に答える
0

差を計算してみましたか？すなわち：最初の数字を取ります。差が最も小さい値を見つけて合計します。完了するまで続行します。最悪の場合、アルゴリズムは O(n^2) の複雑さであり、これは正確には望ましくありませんが、出発点です

于 2013-03-02T13:54:21.297 に答える
0

NP級問題の世界へようこそ！

ブルートフォースまたはリラックスしたアプローチ（シンプレックスアルゴリズムなど）を試すことで最適解を計算できます。これにより、平均ケースの複雑さで多項式時間で解が得られます

于 2013-03-02T14:08:56.053 に答える