1

リスト内の数値の合計が可能な限り最小の差を持つ 2 つのリストに分割する必要がある 10 個の数値を取得します。

だからあなたが得るとしましょう：

10 29 59 39 20 17 29 48 33 45

リストの合計の差ができるだけ小さい 2 つのリストにこれをどのように分類しますか?

したがって、この場合、答えは（私が思うに）次のようになります。

59 48 29 17 10 = 163

45 39 33 29 20 = 166

言語として mIRC スクリプトを使用していますが、perl や C++ も同様に適しています。

編集:実際には、このシナリオのように複数の回答が存在する可能性があります。次の場合もあります。

59 48 29 20 10 = 166

45 39 33 29 17 = 163

私にとっては、最終結果がリストの合計の差ができるだけ小さいということである限り、それは問題ではありません

編集 2: 各リストには 5 つの数字が含まれている必要があります。

4

1 に答える 1

0

あなたがリストしたのはまさにパーティションの問題です（詳細についてはhttp://en.wikipedia.org/wiki/Partition_problemをご覧ください）。要点は、これは NP 完全問題であるため、この問題のインスタンス (つまり、より大きな数) を解決できるプログラムは存在しないということです。

しかし、問題が常に 10 個の数字だけで、それぞれが正確に 5 個の項目からなる 2 つのリストに分割される場合、考えられるすべての解を素朴に試すことも可能になります。 N=10 は整数の数であるため、組み合わせは 2^10=1024 しかなく、それぞれの検証には O(N) しかかかりません (つまり、差を計算します)。

それ以外の場合は、ウィキペディアのページで説明されている貪欲なアルゴリズムを実装できます。実装は簡単ですが、最適性の保証はありません。実際、Java でこの実装を確認できます。

static void partition() {
    int[] set = {10, 29, 59, 39, 20, 17, 29, 48, 33, 45}; // array of data
    Arrays.sort(set); // sort data in descending order
    ArrayList<Integer> A = new ArrayList<Integer>(5); //first list
    ArrayList<Integer> B = new ArrayList<Integer>(5); //second list

    String stringA=new String(); //only to print result
    String stringB=new String(); //only to print result

    int sumA = 0; //sum of items in A
    int sumB = 0; //sum of items in B

    for (int i : set) {
        if (sumA <= sumB) {
            A.add(i); //add item to first list
            sumA+=i; //update sum of first list
            stringA+=" "+i;
        } else {
            B.add(i); //add item to second list
            sumB+=i; //update sum of second list
            stringB+=" "+i;
        }
    }
    System.out.println("First list:" + stringA + " = " + sumA);
    System.out.println("Second list:"+ stringB+ " = " + sumB);
    System.out.println("Difference (first-second):" + (sumA-sumB));
}

良い結果が返されません:

First list: 10 20 29 39 48 = 146
Second list: 17 29 33 45 59 = 183 
Difference (first-second):-37
于 2014-04-04T14:30:54.323 に答える