概要
概要
容量制約の下で価値の合計を最大化する問題です。DP テーブルを使うと、部分問題の積み重ねで考えられます。
動的計画法・再帰 / 0/1 Knapsack（ナップサック問題）
容量制約の下で価値の合計を最大化する問題です。DP テーブルを使うと、部分問題の積み重ねで考えられます。
目次
このページでわかること
概要
容量制約の下で価値の合計を最大化する問題です。DP テーブルを使うと、部分問題の積み重ねで考えられます。
考え方
dp[i][w] = max(not take, take if possible)要点
O(nW)
O(nW)
DP table
品物数 × 容量
補足
各品物について入れるか入れないかを比較します。
行と列の意味を先に固定すると迷いません。
価値と重さを混同しないこと。
動きで確認
ここでは「状態が何か」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。