1

私は 3 分割問題の解決策を見つけました。つまり、n 個の数が与えられた場合、すべてが等しくなる (つまり、各サブセットの合計が n数/3)。

同様の質問が3-PARTITION problem にあります。ただし、以下のコードの説明を探しています。

簡単に言えば、何が起こっているのかわかりません。T が何であるか、i または j が何であるか、k が何であるか、あるいはなぜ k と j が N から始まり、デクリメントされているのか、"T[j + C[i]][k] = true; T[j][k + C[i]] = true」という意味ですか、またはなぜ T[N/3] を返すのでしょうか?

bool T[10240][10000];
bool partition( vector< int > C ) {
    // compute the total sum
    int n = C.size();
    int N = 0;

    for( int i = 0; i < n; i++ ) N += C[i];
    // initialize the table
    T[0][0] = true;
        memset(T, 0, 10000^2);

    // process the numbers one by one
    for( int i = 0; i < n; i++ ) {
                for (int j = N; j >= 0; --j) {
                        for (int k = N; k >= 0; --k) {
                                if (T[j][k]) {
                                        T[j + C[i]][k] = true;
                                        T[j][k + C[i]] = true;
                                }
                        }
                }
        }
    return T[N / 3];
}
4

2 に答える 2

4

まず、戻り値は T[N/3][N/3] である必要があります。

T[i][j] は、合計が i になる最初のパーティションと合計が j になる 2 番目のパーティションを取得できるかどうかを意味します。明らかに、すべての n 個の数の合計は N であるため、T[i][j] が true であることは、配列を合計がそれぞれ i、j、Nij の 3 つのパーティションに分割できることを意味します。

最初は、T[0][0] は true で、その他はすべて false です。つまり、最初は、数値を 0、0、N の 3 つのパーティションに分割することしかできません。i の for ループは、すべての n を反復します。数値であり、毎回、数値 C[i] を最初のパーティションまたは 2 番目のパーティションにグループ化できます。そのため、T[j+C[i]][k] と T[j][k+C[i]] を true に設定します。

変数 j と k が N から始まり、デクリメントされる理由は、1 つの数値を複数回カウントしないようにするためです。たとえば、j が 0 から N までの場合、T[j][k]、T[j+C[i]][k]、T[j+C[i]*2] [k], ... , T[j+C[i]*x][k] はすべて true に設定されますが、これは正しくありません。小さなケースを選んで、自分でプロセスをシミュレートしてみてください。

于 2013-03-26T08:58:36.380 に答える