0

例：

入力: 3, 6, 3 出力: True (3 + 3 = 6 なので)

入力: 3, 2, 6, 4 出力: False (どの組み合わせも等しくならないため)

入力: 4、7、3、6 出力: True (4 + 6 = 7 + 3 なので)

これをコーディングする方法についてアイデアを教えてもらえますか？これをコーディングする方法を始めましたが、数値を追加して比較する方法について混乱しています

4

5 に答える 5

3

魔法の言葉 (「パーティション問題」、「動的プログラミング」など) を知らなくても、答えの大きな本 (ウィキペディアなど) を参照する方法を説明します。

入力から未使用の最大数のインスタンスを 1 つ取得し、それを 2 つのグループのいずれかに割り当てると、問題は同じ問題の (一般化されたバージョンの) より小さなインスタンスに縮小されます。

一般化された問題は、2 つのグループの合計の差が特定の非負の整数になるように、入力数値を 2 つのグループに分割できるかということです。

入力数値が 4、3、2、1 で、グループの合計の差が 0 になるように 2 つのグループを作成する必要があるとします。

グループの 1 つに 4 を割り当てます。この特定のケースでは、どのグループでも問題ありません。

残りの入力数値は 3、2、1 であり、既に扱った 4 を無視して、グループの合計の差が 4 になるように、これら 3 つの数値を 2 つのグループにする必要があります。 4 をグループの 1 つに割り当てて作成した 2 つのグループの違いです。) 約束どおり、これは元のタイプの問題のより小さなインスタンスです。

問題は、5、5、4、3、3 (ウィキペディアの「パーティションの問題」にある例) のように、次の数字をどのグループに入れる必要があるかが明確でない場合があることです。自分が行ったことを記録しておくと、最後の試みがうまくいかなかったことがわかったときに、戻って (「バックトラック」)、別の方法を試すことができます。

5, 5, 4, 3, 3 {} {}
   5, 4, 3, 3 {5} {}
      4, 3, 3 {5} {5}
         3, 3 {5, 4} {5}
            3 {5, 4} {5, 3}
              {5, 4} {5, 3, 3} NO - backtrack
              {5, 4, 3} {5, 3} NO - backtrack
            3 {5, 4, 3} {5}
              {5, 4, 3} {5, 3} NO - already tried - backtrack
              {5, 4, 3, 3} {3} NO - backtrack
         3, 3 {5} {5, 4} NO - symmetric to what we already tried - backtrack
      4, 3, 3 {5, 5} {}
         3, 3 {5, 5} {4}
            3 {5, 5} {4, 3}
              {5, 5} {4, 3, 3} YES

すぐに答えを得ることができますか？まあ、これは尋ねられた質問ではありませんが、バックトラックの複雑さを考えると、尋ねるのは自然なことです. 答えは、いいえ、世界史上最も賢い人が私たちのために働いていたとしても、そうではありません. この種の問題がどのようなインスタンスに与えられても、迅速に実行されることが保証されているメソッドを見つけた人は誰もいません。おそらく、これらの問題の多くのインスタンスに対してかなりうまく対処できますが、一般的に、平均して、この種のことを行うプログラムは遅くなる運命にあります。

于 2013-03-14T02:42:56.260 に答える
2

これは、NP完全であるパー​​ティションの問題です。それにもかかわらず、使用できる動的計画法ソリューションがあります。ウィキペディアの記事を参照してください。

http://en.wikipedia.org/wiki/Partition_problem

于 2013-03-14T03:15:11.087 に答える
0

わかった！総当たり計算を使用して、可能なすべてのオプションをチェックします

int[] numbersArray = new int[10];
int sum = 0;

for(int j = 0; j < numbersArray.lenght;j++) // sum
   sum += numbersArray[j];



for(int i = 0; i < numbersArray.lenght;i++)
{
   int numChecking =  numbersArray[i]; // right half .. 

   if((sum-numChecking) == numChecking)
     return true;

}
return false;

// 私はそれをテストしていませんが、これはすべての可能性を 1 つの値でチェックします..

于 2013-03-14T18:52:19.423 に答える
0 
public class Weirdie {
private boolean calculate(int[] array) {
    boolean match = false;
    List<Integer> list = new ArrayList<Integer>();
    int length = array.length;
    for(int i=0;i<length;i++) {
        for(int j=i+1;j<length;j++) {
            int sum = array[i] + array[j];
            if(list.contains(sum)) {
                match = true;
                break;
            } else {
                list.add(sum);
            }
        }
        if(match) {
            break;
        }
    }
    return match;
}

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] array = { 3, 6, 3, 4, 8};
    int[] array2 = { 3, 2, 6, 4};
    int[] array3 = { 4, 7, 3, 6 };
    Weirdie  w = new Weirdie();
    System.out.println(w.calculate(array));
    System.out.println(w.calculate(array2));
    System.out.println(w.calculate(array3));
}

}

実際、私はまだあなたの要件を混乱させています.あなたの説明のように、3 + 3 = 6のため、数値グループ1 {3,6,3}はtrueを出力します.そして、あなたは数値グループ2 {3,2,6,4}が出力すると言いました. falseですが、2+4=6も条件に合っているようです。3番目の数字グループで、数字グループ1がtrueを出力する理由は、3+6=6+3だと思います。

于 2013-03-14T04:53:29.790 に答える