導入

0 - 1ナップサック問題は、動的計画法を理解するための一種のナップサック問題である.その兄弟とは異なり:分数ナップサック、貪欲は、この問題の最適解を保証しません.動的計画法を用いて解く.ここでは、我々はオブジェクトを拾うことができるか、それを残すことができます.オブジェクトの端数を選択できません.

問題記述

私たちが重さとそれらに関連した値を持つn個のオブジェクトを与えられていると仮定します.また、容量= maxweightとナップザックを与えられている.私たちの目標は、私たちの最大重量をオーバーシュートしないことを念頭に置いている間、ほとんどの値と最小の重量でそれらを選ぶことによって、これらのオブジェクトの最大の利益を得ることです.各オブジェクトは一度だけ選択するか、まったく選択できません.
例えば、

Input:
n=4
maxWeight=5
weights={4,3,5,1}
value={1,2,2,3}

Output:
5

この場合、値2,3の重み3,1のオブジェクトは合計値＝5となる.どちらが最大です.

観察

ここで、キーの観測は、重み合計がナップサックの容量以下であり、最大値和を持つ重みのサブセットを見つける必要があることです.

なぜ貪欲なのか？

貪欲は分数ナップサックのために働くが、0 - 1ナップサックのために働きません.ここでは、0 - 1ナップサックのための貪欲なアプローチを無効にする例です.w = 6と項目を仮定します.

Item   Value   Size   Value/Size
A       5.5       4         1.38
B       4          3         1.33
C       4          3         1.33

0 - 1ナップサックについては、あなたが貪欲なアプローチを適用する場合は、最高の値/サイズie . item .を持つアイテムをピックアップします.さて、あなたはこれ以上の項目を選ぶことはできません.それは、あなたがバッグに持っている唯一のものは、22の合計値である商品Aであることを意味します.
他方では、貪欲ではなく、最も貴重なアイテムを取っていて、代わりにアイテムBを取ったならば、あなたは同様にアイテムCを取る十分な余地があるでしょう.これは袋の中で合計24の値になり、貪欲なルートより良い.

Dynamic Approach

我々は、最終的な答えを計算するのに役立ちます小さなサブ問題に解決策を格納するための2 D配列を使用します.ここでは再帰的アプローチで述べたのと同じ2つの操作を行います.

物を拾う

私たちがi(th)オブジェクトを拾うことに決めるならば、利益は残りの重さIEのためにそのオブジェクト+最適化された答えの価値になります

オブジェクトを残す

我々がオブジェクトを去ると決めるならば、利益はその重さie .のための最適化された答えです

特定のオブジェクトの答えは、これらの2つの値の最大値になります.

主な条件

dp[i][c] = max (dp[i-1][c], profits[i] + dp[i-1][c-weights[i]]);

int knapsack(int v[], int w[], int n, int W)
{
    int T[n+1][W+1];
    for (int j = 0; j <= W; j++) {
        T[0][j] = 0;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= W; j++)
        {
            if (w[i-1] > j) {
                T[i][j] = T[i-1][j];
            }
            else {
                T[i][j] = max(T[i-1][j], T[i-1][j-w[i-1]] + v[i-1]);
            }
        }
    }
    return T[n][W];
}

時間の複雑さ
空間の複雑さ2次元アレイTを余分空間とした