ナップザック問題

2025年10月20日

“`

ナップザック問題

英語表記: Knapsack Problem

概要

ナップザック問題は、「容量が限られたナップザック（リュックサック）に、重さや価値が異なる複数の品物の中から、合計価値が最大になるように品物を詰め込むにはどうすればよいか」を問う、組み合わせ最適化問題の代表例です。この問題は、アルゴリズムと計算量の分野において、特に「動的計画法（Dynamic Programming: DP）」の適用例として非常に有名であり、その理解はDPを習得する上での最初の大きなステップとなります。限られたリソース（容量）の中で最大の成果（価値）を得るという構造が、情報科学における多くの最適化問題の基礎を形成しています。

詳細解説

ナップザック問題が「アルゴリズムと計算量」の中の「動的計画法」の「典型問題」として扱われる理由は、その構造が「最適性の原理」を満たし、より小さな部分問題に分割できる点にあります。

問題の構成要素と種類

この問題は、主に以下の要素で構成されています。

品物群: それぞれ重さ（$w_i$）と価値（$v_i$）が設定されています。
ナップザック容量: 詰め込むことのできる最大の重さ（$W$）が定められています。
目的: 容量$W$を超えない範囲で、品物の合計価値を最大化することです。

特にIT資格試験で問われるのは、「0-1ナップザック問題」です。これは、各品物について「入れる（1）」か「入れない（0）」の二択しか許されないバージョンで、これが動的計画法で最も効率的に解ける形になります。

なぜ動的計画法が必要なのか

一見、価値の高いものから順に詰め込めば良い「貪欲法（Greedy Algorithm）」で解けそうに思えますが、単純な貪欲法では必ずしも最適解にたどり着けません。例えば、容量が10kgのとき、(A: 9kg, 100万円)と(B: 5kg, 50万円)、(C: 5kg, 50万円)があったとします。貪欲にAを選ぶと容量を使い切り100万円で終わりますが、BとCを選ぶと合計10kgで100万円となり、この例では結果は同じです。しかし、品物の組み合わせが複雑になると、目先の最適解が全体最適を阻害してしまうケースが頻繁に発生します。

動的計画法は、このような状況を回避するために、「容量$w$のナップザックに品物$i$までを考慮して詰め込んだときの最大価値」という部分問題の最適解を、表（テーブル）に記録しながら、より大きな問題の最適解を段階的に求めていく手法です。

動的計画法による解法（漸化式）

動的計画法では、以下の漸化式（状態遷移）を用いて問題を解き進めます。

$DP[i][w]$：「$i$番目までの品物を使って、容量$w$のナップザックに詰め込んだときの最大価値」と定義します。

$i$番目の品物について、以下の二つの選択肢を比較します。

$i$番目の品物を入れない場合: 最大価値は$DP[i-1][w]$と同じです。
$i$番目の品物を入れる場合: 最大価値は、$DP[i-1][w – w_i]$（$i$番目の品物を入れる前の残りの容量での最大価値）に$v_i$（$i$番目の品物の価値）を加えたものになります。ただし、品物の重さ$w_i$が現在の容量$w$を超えない場合に限ります。

最終的な漸化式は、この二つの選択肢のうち、価値が大きい方を選択することになります。

$$
DP[i][w] = \max \left( DP[i-1][w], \quad DP[i-1][w – w_i] + v_i \right)
$$

このように、過去の計算結果（部分問題の最適解）を再利用しながら、最終的な$DP[N][W]$（全品物を使って容量$W$での最大価値）を求めるのが動的計画法の醍醐味であり、ナップザック問題がこの技法の理解に不可欠とされる所以なのです。計算量は品物の数$N$と容量$W$に比例するため、非常に効率的です。

具体例・活用シーン

ナップザック問題は、その構造が現実世界における「リソースの制約下での最適化」と完全に一致するため、非常に多くの分野で活用されています。

応用例

リソース配分と予算編成: 企業が限られた予算（容量）の中で、複数のプロジェクト（品物）に資金を配分し、最大の利益（価値）を得るための投資計画の策定。
貨物輸送の最適化: 輸送機やトラックの積載量（容量）を上限として、運ぶ荷物（品物）の組み合わせを決定し、輸送効率（価値）を最大化する。
広告枠の最適化: 広告主が限られた時間枠や予算の中で、最も効果の高い広告の組み合わせを選ぶ。

アナロジー：泥棒のジレンマ

この問題を初心者の方に理解していただくための有名なアナロジーがあります。

ある泥棒が美術館に侵入しました。泥棒が持っているナップザックは、重さの制限（例えば20kg）があります。目の前には、重さも価値も異なる様々な美術品が並んでいます。

壺A: 5kg, 100万円
絵画B: 15kg, 400万円
宝石C: 2kg, 30万円
彫像D: 10kg, 250万円

泥棒の目的は、この20kgという制約の中で、盗んだ品の合計価値を最大にすることです。

もし泥棒が「貪欲法」を使うと、まず価値の高い絵画B (15kg, 400万円)を選びます。残りの容量は5kgです。宝石C (2kg, 30万円)と壺A (5kg, 100万円)を比べると、壺Aは重すぎて入りません。仕方なく宝石Cを選び、合計430万円で終了します。

しかし、「動的計画法」の考え方を持つ賢い泥棒は、まず「容量1kgなら何が最大か」「容量2kgなら何が最大か」という小さな問題の最適解を心の中でシミュレーションします。

そして、最終的に「壺A (5kg, 100万円)と彫像D (10kg, 250万円)と宝石C (2kg, 30万円)の組み合わせ（合計17kg, 380万円）」や、「絵画B (15kg, 400万円)と宝石C (2kg, 30万円)の組み合わせ（合計17kg, 430万円）」など、すべての組み合わせを計算するのではなく、過去の最適解を利用して効率的に最大価値（この例では430万円の組み合わせ）を見つけ出すのです。この「小さな容量での最善の選択」の積み重ねこそが、動的計画法の本質であり、ナップザック問題の解法なのです。

資格試験向けチェックポイント

ナップザック問題は、基本情報技術者試験や応用情報技術者試験において、「アルゴリズムと計算量」の分野で頻出する非常に重要なテーマです。

1. 動的計画法（DP）の理解

出題パターン: ナップザック問題がDPで解ける理由を問う問題が出ます。特に「最適性の原理」が適用されること、すなわち「部分問題の最適解が、元の問題の最適解に含まれる」という性質を理解しているかが重要です。
対策: 貪欲法や分枝限定法との違いを明確に説明できるようにしてください。DPは、重複する部分問題を一度だけ計算し、その結果を再利用することで計算効率を高めている点を押さえましょう。

2. 計算量の概念

出題パターン: ナップザック問題は、一般に「NP困難」な問題群に分類されますが、0-1ナップザック問題は、動的計画法を用いることで、品物の数$N$と容量$W$に対して$O(NW)$という多項式時間で解くことができます（擬似多項式時間）。この計算量の特徴や概念的な位置づけを問う問題が出ます。
対策: $O(NW)$が多項式時間と見なされるのは、実務上$W$がそれほど大きくない場合や、容量が整数値に限定される場合です。この「擬似多項式時間」という概念は、応用情報技術者試験で特に重要になります。

3. 具体的なアルゴリズムのトレース

出題パターン: 問題文で品物の重さと価値、容量が与えられ、DPのテーブル（表）の一部を埋める、または最終的な最大価値を計算させる問題が出ることがあります。
対策: 小さな例題（品物3つ、容量5など）を用いて、実際に上記の漸化式を適用し、DPテーブルがどのように埋まっていくかを自力でトレースする練習を積んでください。これは、DPの仕組みを体感的に理解する上で最も効果的な学習法です。

4. 関連アルゴリズムとの比較

分枝限定法: ナップザック問題を解く別の手法として、分枝限定法（Branch and Bound）があります。これは探索空間を木構造で表現し、効率の悪い枝を切り捨てながら最適解を探す手法です。DPが「すべての容量パターン」を網羅的に計算するのに対し、分枝限定法は探索の効率化に焦点を当てています。応用情報技術者試験では、これらの比較も重要です。