0-1 ナップサック問題
容量の決まったナップサックに品物を詰めて価値を最大化する問題を、DP テーブルが 1 マスずつ埋まる様子で理解します。
品物（重さ・価値を編集できます）
8
埋めるステップ
0
最大価値（最適解）
—
選ばれる品物
—
使う重さ / 容量
—
計算中のマス
入れない（真上）
入れる（左＋価値）
復元した最適経路
各品物は「入れる / 入れない」の 2 択（だから 0-1）。重さの合計が容量を超えない範囲で価値の合計を最大化します。
DP テーブル
各マスは 「品物 i を入れない」（真上のマス）と 「入れる」（重さぶん左のマス＋価値）の 大きい方で決まります。
DP テーブル
dp[i][w] ＝「最初の i 個の品物まで考え、容量 w のときの最大価値」。各マスは 「品物 i を入れない」（真上のマス）と 「入れる」（重さぶん左のマス＋価値）の 大きい方で決まります。
いま計算しているマス
ここが DP の本質
- 大きな問題（全品物・容量 W）を 「最初の i 個・容量 w」という小さな部分問題に分けて表に並べる。
- 各マスは すでに埋めた上の行のマス 2 つだけを見れば決まる ── 全組合せ（2n 通り）を試さない。
- 全マスを埋め終えたら右下が答え。逆向きにたどると「どの品物を選んだか」が復元できる。