0/1 ナップサック

容量制限内で物品を選び、各物品は一回だけ取るか、取らないかです。DP は物品の各接頭部と各容量の最大価値を保存し、O(n × capacity) 時間で解きます。このレッスンは正整数の重さと整数容量を使います。

i 番目の物品を使う判断では、まだその物品がない問題を表す一行上だけを読みます。同じ物品の二重使用を防ぐ規則です。

0/1 ナップサックの仕組み

dp[i][w] は先頭 i 物品だけを使い、容量 w で得る最大価値。物品なしの行 0 は 0、正重量なので列 0 も 0 です。

行ごとに容量を左から埋めます。重すぎれば skip = dp[i - 1][w] だけです。入る場合は次も比べます。

take = value + dp[i - 1][w - weight]

大きい方を採用します。重要なのは両方が i - 1 行を読むこと。同じ行から take を読むと、現在物品を再使用し、個数無制限の規則になります。

完成後は dp[n][capacity] から逆追跡します。上と等しければ、この同点規則では取らず、違えば取り、重さを容量から引いて一行上へ戻ります。

計算をステップで追う

既定容量は 9 です。

1. 基底行と列を 0 にする。後の候補は最終的にここへ依存する。
2. A：容量 1 は入らず 0。2 では dp[1][0] でなく dp[0][0] を読んで 3。行は 0, 0, 3, 3, 3, 3, 3, 3, 3, 3。
3. B：容量 1、2 は上をコピー。3 で B の 4。5 では dp[1][2] = 3 に加え、B+A は 4 + 3 = 7。容量 9 まで 7。
4. C：容量 4 は 8、6 の C+A は 11、7 の C+B は 12。9 では上一行の容量 5 と合わせて 15。
5. D：価値は同じ 8 でも重さ 5。容量 6 は skip = 11、take = 8 で取らない。8 は両方 12 で skip。9 は 8 + dp[3][4] = 8 + 8 = 16 で take。
6. E：単品価値は最大の 10。容量 8 を 13 に改善するが、9 では旧 16 に負ける。最大の単品が最良の組とは限らない。
7. 逆追跡：dp[5][9] = 16 から、上と同じなので E を取らない。D を取り容量 9→4、C を取り 4→0、B と A は取らない。C+D、重さ 9、価値 16。

時間・空間計算量

容量の数値に依存する擬多項式時間です。容量を二進数で表す入力ビット数だけの多項式とは異なります。

境界ケース

• 容量 0 は価値 0、選択なし。
• 重すぎる物品は一行上をコピーする。
• 何も入らなければ答えは 0。
• ちょうど入る take は、残容量の列 0 を参照する。
• 同点は一貫した規則が必要。ここでは skip を優先し、同じ逆追跡結果を得る。

よくある間違い

• dp[i][w - weight] を読む。 現在物品を再使用し、0/1 でなくなります。
• 絶対価値で貪欲に選ぶ。 greedy-trap は A の 30 に対し、DP が B+C の 56 を得ます。価値重量比の反例ではなく、B と C は比率も良い例です。
• 基底行列を省く。 初物品と零容量の処理が各所の特別分岐になります。
• 前向きに選択を復元する。 最終セルから上と比較し、後ろへたどります。
• 単位を混ぜる。 重さと容量は同単位、価値は別の点数です。価値を重さに足せません。

簡略化の範囲

二次元表は一行上への依存を示します。値だけなら一行へ圧縮できますが、容量は大きい方から更新し、同じ物品を再利用しないようにします。選択集合の復元には対応する情報も必要です。小整数と少数物品は表示のためで、漸化式は大きい入力にも使えます。