2

動的計画法でナップザック0-1の問題を解決する方法は知っていますが、O（N * C）（Nアイテム、C容量）の複雑さを損なうことなく、どのアイテムを取るかを判断するのに苦労しています。

何かアイデアはありますか（ボトムアップアプローチをお勧めします）？

4

6 に答える 6

3

今、結果を配列bool[] aに格納していると仮定します。ここa[i]で、合計iが達成できる場合はtrueです。
別の配列が必要になります。int[] bここで、b[i]は合計を達成するためにナップザックに配置した最後の要素ですi。

だから、あなたが持っていた場所

a[i] = true;

あなたは必要になるでしょう

a[i] = true;
b[i] = current_item;

次に、合計を達成するためにどの項目を取ることができるかを見つけることiは単純なループです。

PS簡単にするために2つのアレイを使用していますが、明らかにアレイaは削除できます。

于 2011-02-08T16:35:09.083 に答える
3

O（n）回でパスを再構築するための変更は次のとおりです

int knapsack(int weight[], int profit[], int no_of_items, int capacity) {
    for (int var = 0; var <= capacity; ++var) {
        dp[0][var] = 0;
    }
    for (int var = 0; var <= no_of_items; ++var) {
        path[var] = false;
    }
    int using_item_i, without_using_item_i;
    for (int i = 1; i <= no_of_items; ++i) {
        for (int j = 1; j <= capacity; ++j) {
            without_using_item_i = dp[i - 1][j];
            using_item_i = 0;
            if ((weight[i]) <= j) {
                using_item_i = dp[i - 1][j - weight[i]] + profit[i];
            }

            if (using_item_i >= without_using_item_i) {
                taken[i][j] = true;
                dp[i][j] = using_item_i;
            } else {
                taken[i][j] = false;
                dp[i][j] = without_using_item_i;
            }
        }
    }
    //Reconstructing back the path
    int j = capacity;
    for (int i = no_of_items; i >= 0; --i) {
        if (taken[i][j]) {
            path[i] = true;
            cnt++;
        }
        j = j -  weight[i];
    }
    return dp[no_of_items][capacity];
}
于 2015-01-05T16:45:34.107 に答える
1 
boolean[] solution = new boolean[nItems];

for (int i = nItems, c = maxCapacity; i > 0 && c > 0; i--) {
    int iThItemAddedValue = value[i - 1][c - weights[i - 1]] + values[i - 1];
    int iThItemInheritedValue = value[i - 1][c];

    if (iThItemAddedValue > iThItemInheritedValue) {
        solution[i - 1] = true;
        c = c - weights[i - 1];
    } else {
        solution[i - 1] = false;
    }
}
于 2015-01-04T14:22:21.043 に答える
1

添付画像のソルをご確認ください以下の画像にはスニペットがあります

于 2017-01-01T23:19:34.877 に答える
0

https://www.dropbox.com/s/ish7t5vgy91fovt/Screenshot%202017-01-01%2015.16.31.png?dl=0

呼び出し元で tmpList を出力すると、答えが得られます

于 2017-01-01T23:15:42.360 に答える