ナップサック問題とは？
0/1ナップサック問題(0/1 Knapsack)は、重さの上限が決まったバッグに、それぞれ重さと価値を持つ品物を選んで入れ、価値の合計を最大にする問題です。各品物は丸ごと入れる(1)か入れない(0)かのどちらか — 分割できません。
品物ごとに「入れる/入れない」の2択なので全探索は2ⁿに爆発します。動的計画法(DP)は重なる部分問題を表に保存しO(nW)に削減します。
状態の定義
dp[i][w] = 先頭からi個の品物まで考え、重さ上限がwのときに得られる最大価値。
こう定義すると、品物を1つ多く見るとき「今の品物を入れるか」だけ決めればよいように問題が分かれます。
漸化式
i番目の品物の重さが wt、価値が v なら
- •入れない:
dp[i-1][w](上限そのまま、価値そのまま) - •入れる(w ≥ wt のとき):
dp[i-1][w - wt] + v(入れた重さ分だけ上限を引き価値を足す) - •
dp[i][w] = max(入れない, 入れる)
2択のうち価値が大きい方を選ぶだけです。
動作原理
ステップ1. dp[0][*] = 0(品物がなければ価値0)で初期化します。
ステップ2. 品物iを1つずつ増やし、全ての重さ上限wに対し上の漸化式で表を埋めます。
ステップ3. dp[n][W] が答え(全品物・最大上限での最大価値)です。
1次元最適化: 1行 dp[w] だけ持ち、wを大きい方から小さい方へ更新すると空間がO(W)に減ります。
AlgoNoteの可視化は、表が1マスずつ埋まり「入れる/入れない」のどちらが選ばれるかをステップごとに示します。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(nW) |
| 空間 | O(nW) または O(W) |
nは品物数、Wは重さ上限です。
例で追ってみる
品物 (重さ, 価値) = (1, 6), (2, 10), (3, 12)、上限 W=5。
- •品物1だけ: 上限5で価値6
- •品物1·2: (1,6)+(2,10) を両方入れ重さ3·価値16
- •品物1·2·3: (2,10)+(3,12) → 重さ5·価値22 → 最大22
dp[3][5] = 22 が答えです。
よくあるミス
- •1次元の更新方向:
dp[w]を小さいwから更新すると同じ品物を何度も入れられます(それは「無限ナップサック」)。0/1は必ず大きいwから。 - •上限チェックの欠落:
w ≥ wtのときだけ入れる分岐を適用し負のインデックスを避けます。 - •Wが巨大なとき: O(nW)が重いなら価値基準DPなど別の定義を検討します。
AlgoNoteで直接確認しましょう
各品物で「入れる」と「入れない」の価値を比べ表が埋まる過程をAlgoNoteでステップごとに確認できます。