4

作業をより迅速かつ効率的に行うために、Java アプレットを作成しています。

ユーザーは、アイテムのリストを分割する必要がある 3 つのグループのサイズを定義します。リスト内の各項目は、3 つのグループのどれに配置されるかに基づいて、異なる値を持ちます。アプレットは、合計値が最も高い組み合わせを表示する必要があります。

例: 列を持つ整数の 2D 配列。項目番号、グループ 1 の値、グループ 2 の値、およびグループ 3 の値。

16   2   2   5
19   6   0   3
24   1   4   4
25   4   2   3
27   4   2   3
29   3   3   3
31   5   3   1
32   5   2   2

これにより、ユーザーはグループ 1 に 3 つのスロット、グループ 2 に 3 つのスロット、グループ 3 に 2 つのスロットを定義します。

アプレットは、順不同で次のソリューションを表示する必要があります。

Group 1: 19, 31, 32
Group 2: 24, 27, 29
Group 3: 16, 25
OR
Group 1: 19, 27, 32
Group 2: 24, 29, 31
Group 3: 16, 25
OR
Group 1: 19, 31, 32
Group 2: 24, 25, 29
Group 3: 16, 27
OR
Group 1: 19, 25, 32
Group 2: 24, 29, 31
Group 3: 16, 27

考えられるすべての順序で配列を実行するあまり効率的ではない方法を管理できますが、重複するソリューション (つまり、16,25 と 25,16) が生成されます。配列をシャッフルしなくても、考えられるすべての組み合わせを合計する方法があると確信しています。現時点では頭を包むことはできません。もしあなたの誰かがこれのための方法を持っていれば、私は最も感謝しています.

4

2 に答える 2

0

更新: 動的計画法を使用した新しいアプローチ

（古いもの：）

貪欲なアプローチを使用できると思います。アイデアは次のとおりです。

  1. 表の最大値を見つけます。対応するアイテムを対応するグループに入れます。
  2. テーブルからアイテムの対応する行を削除します。
  3. グループがいっぱいになったら、グループの対応する列を削除します。

上記のアイデアを実装するには、配列used[]を使用して、アイテムが使用されている (既にグループに入れられている) かどうかを認識し、3 つの最大ヒープを使用して、テーブル内の 3 つの値列を表すことができます。ヒープ要素は（値がキー）のようです。3 つのヒープがH[0]、H[1]、および であるとしH[2]ます。アルゴリズムは次のようになります。

Init bool array `used[n]` to all false 
Init heap array `H[3]`
Init int array `capacity[3]` to required group sizes
for(int i from 0 to n-1){
    int v = -1, heap_number, item_number;
    for(int j from 0 to 2){
        if(capacity[j] == 0){
            continue;
        }
        while(used[H[j].top().item_number]){
            H[j].pop();
        }
        if(H[j].top().value > v){
            v = H[j].top().value;
            heap_number = j;
            item_number = H[j].top().item_number;
        }
    }
    Assign Item item_number to Group heap_number
    used[item_number] = true;
    capacity[heap_number]--;
}

これが私の新しいアプローチである動的プログラミングのアプローチです。

  • f[i][j][k]それぞれ i、j、および k 個のスロットが残っているグループ 1、2、および 3 の解を表すと仮定します。解決策は、項目からグループへの割り当てを記録する 3 つのリストです。と仮定しa = i + j + kます。
  • 状態遷移方程式: f[i][j][k] = max{f[i-1][j][k] + Item[a].value_1, f[i][j-1][k] + Item[a].value_2, f[i][j][k-1] + Item[a].value_3}.
  • 初期状態: f[0][0][0] = 0。
  • 最終的な答え: f[group_1_size][group_2_size][group_3_size].
于 2013-11-09T21:32:31.947 に答える
0

私は解決策を考え出すことはできませんが、あなたの質問に答える - すべての可能な合計を実行することについて - 再帰を使用できます。

// @row - currently processed row
// @g1, g2, g3 - arrays with numbers of rows put in respective group
// @options - for results
// @rows - source array
void PROCESS_ROW(int row, int[] g1, int[] g2, int[] g3, int[][][][] options, rows) {
    if (row >= rows.length) {
        // Recursion ended, collecting generated distribution
        options[].push_back(new int[3][][]);
        options[last][0] = g1.clone();
        options[last][1] = g2.clone();
        options[last][2] = g3.clone();
        return;
    }
    // Trying to put row in each group consequently
    if (g1.length < g1_slots) {
        g1.push_back(row);
          PROCESS_ROW(row + 1, g1, g2, g3, options, rows);
        g1.pop_back();
    }
    if (g2.length < g2_slots) {
        g2.push_back(row);
          PROCESS_ROW(row + 1, g1, g2, g3, options, rows);
        g2.pop_back();
    }
    if (g3.length < g3_slots) {
        g3.push_back(row);
          PROCESS_ROW(row + 1, g1, g2, g3, options, rows);
        g3.pop_back();
    }
}

int[][] rows;
// .. fill
int[][][][] options;

PROCESS_ROW(0, new int[], new int[], new int[], options, rows);
// now options contains all possible groupings

実際、このコードは Java ではないため、適合させる必要があります。また、g1_slots なども引数として関数に渡す必要がありますが、詳細です。その考えは理解できる。また、最初の部分に強力な処理を含めてif、合計を計算し、可能な組み合わせとともに最高のものを保存することも非常に可能です。そして、より高い合計が発生するたびに配列をクリアします。
そしてもちろん、この解決策は、行が16、19、25ではなく、0、1、2..の数字を持つことを意味します...したがって、Map rows配列の代わりに使用して、この側面を再度調整する必要があります。しかし、私が言ったように、それは詳細です。

于 2013-11-09T22:39:24.670 に答える