0/1 ナップサック問題｜コードで実践

0/1 ナップサック問題

このレッスンで分かること

計算量は O(n * capacity)、メモリも O(n * capacity) です

DP の代名詞ともいえる 0/1 ナップサック問題 に挑戦します

「0/1」というのは、各品物を 取るか取らないかの 2 択 で、同じ品物を 2 個入れることはできない、という意味です

0/1 ナップサック問題とは

重さと価値を持つ品物を限られた容量に詰め、価値合計を最大化する古典的な 2 次元 DP 問題に挑む。本レッスンでは、0/1 ナップサック問題の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

DP の代名詞ともいえる 0/1 ナップサック問題 に挑戦します。容量 capacity のリュックに、weights (重さ) と values (価値) のペアで表される n 個の品物を詰めるとき、合計重さが capacity を超えない範囲で 価値の合計を最大化 する問題です。

「0/1」というのは、各品物を 取るか取らないかの 2 択 で、同じ品物を 2 個入れることはできない、という意味です。重さも価値も整数とします。

ナップサック問題は「取る / 取らない」の選択を全品目について考える、2 次元 DP の代表例。

状態の設計

ここまでの DP は配列 1 本でしたが、ナップサックでは 2 次元の状態 を使います。dp[i][w] を「最初の i 個の品物までを考えたとき、容量 w で実現できる最大価値」と定義します。最終的に欲しいのは dp[n][capacity] です。

遷移は次のように書けます。

品物 i-1 を 取らない 場合、dp[i][w] = dp[i-1][w]
品物 i-1 を取る場合 (w >= weights[i-1] のとき)、dp[i][w] = dp[i-1][w - weights[i-1]] + values[i-1]

両者の 大きい方 が dp[i][w] です。基底ケースは dp[0][w] = 0 (品物がないなら価値 0)。

diagram (will load when visible)

図のポイント (テキスト併記)

この「取る / 取らない」の二択遷移は、後の 部分集合和 や LCS にも応用が利く考え方です

この「取る / 取らない」の二択遷移は、後の 部分集合和 や LCS にも応用が利く考え方です。

「最後の品物をどう扱うか」で場合分けする。これは DP の典型的なフレームワーク。

Python での実装

Python

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi = weights[i - 1]
        vi = values[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]
            if w >= wi and dp[i - 1][w - wi] + vi > dp[i][w]:
                dp[i][w] = dp[i - 1][w - wi] + vi
    return dp[n][capacity]

2 次元配列 dp を (n+1) x (capacity+1) で確保し、i = 1..n、w = 0..capacity の二重ループで埋めます。各セルは「取らない」値で初期化してから、w >= wi ならば「取る」値と比較して大きい方に更新する流れです。

計算量は O(n * capacity)、メモリも O(n * capacity) です。容量を 1 次元に圧縮することもできますが、まずは素直な 2 次元版を理解しましょう。

JavaScript での実装

JavaScript

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    const wi = weights[i - 1];
    const vi = values[i - 1];
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i - 1][w];
      if (w >= wi && dp[i - 1][w - wi] + vi > dp[i][w]) {
        dp[i][w] = dp[i - 1][w - wi] + vi;
      }
    }
  }
  return dp[n][capacity];
}

JavaScript では Array.from({ length: n + 1 }, ...) で 2 次元配列を作るのが定石です。new Array(n + 1).fill(...) でやると参照が共有されてしまうので注意。

よくある間違い

1 つ目は インデックスのずれ。dp[i][w] は「i 個まで考えた」状態なので、注目する品物は weights[i - 1]、values[i - 1] です。i でアクセスすると配列外参照になります。2 つ目は 2 次元配列を [[0] * (capacity + 1)] * (n + 1) で作る。Python ではこの書き方だと 同じリストが共有される ため、1 行更新すると全行が変わってしまいます。リスト内包表記で書き直しましょう。3 つ目は 0/1 ではなく無限個 OK と混同。同じ品物を複数回取れる「完全ナップサック」になると、内側ループの方向が変わります。

やってみよう

容量 capacity = 7、weights = [3, 4, 5]、values = [4, 5, 6] で試す。答えは 9 (3+4 = 重さ 7、価値 4+5=9)。
dp 配列を 2 次元の表として出力してみる。i 軸と w 軸で最大値が右下に向かって伝播するのが分かる。
1 次元配列に圧縮した版に挑戦する。w を降順で更新するのがコツ。

0/1 ナップサックは「取る / 取らない」の二択 DP。状態 (i, w)、遷移 max(取らない, 取る)、基底 dp[0][w] = 0 の 3 点セットを覚えれば、類題は自力で書けるようになる。

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. 計算量はどう求めれば良いですか？

A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

Q. 覚えるべき定番アルゴリズムは何ですか？

A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

次のレッスン

次は 最長共通部分列 (LCS) で、重さと価値を持つ品物を限られた容量に詰め、価値合計を最大化する古典的な 2 次元 DP 問題に挑むを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

0/1ナップサックの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 0/1ナップサックとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

0/1 ナップサック問題