System Note
$ cat /proc/ai-disclosure
本記事の構成および論理分析にはAI（人工知能）を使用しています。情報の正確性は、システム管理者（UNIXユーザー）による手動検証済みです。
【ナップサック問題で遊ぼう】Pythonで全探索から動的計画法まで｜定番問題をコードパズルにしてみた
アルゴリズムを学んでいると、よく登場する定番問題に 「ナップサック問題」 があります。
名前だけ聞くと少し難しそうですが、やっていることはとても身近な問題です。重さと価値の違う品物がいくつかあり、ナップサックに入れられる重さには上限があります。その中で、できるだけ価値が高くなるように品物を選ぶ、という小さなパズルです。
今回は、このナップサック問題をPythonで遊びながら見ていきます。最初は全部の選び方を試す素直な方法から始めて、最後は動的計画法（DP）で効率よく解くところまで進みます。
目次
ナップサック問題ってなに？
本題に入る前に、少しだけ ナップサック問題 のルールを整理しておきます。
たとえば、次のような品物があるとします。
| 品物 | 重さ | 価値 |
|---|---|---|
| A | 2 | 3 |
| B | 1 | 2 |
| C | 3 | 4 |
| D | 2 | 2 |
ナップサックの容量は 5 です。
このとき、合計の重さが 5 以下になるように品物を選び、その中で価値の合計を一番大きくします。
- Aを入れる？ 入れない？
- Bを入れる？ 入れない？
- Cを入れる？ 入れない？
- Dを入れる？ 入れない？
ひとつひとつの品物について「選ぶ」か「選ばない」かを決めるので、これは 0/1ナップサック問題 と呼ばれます。同じ品物を何度も入れることはできません。
Pythonでは、重さと価値を次のようなリストで表せます。
weights = [2, 1, 3, 2]
values = [3, 2, 4, 2]
capacity = 5目標は、capacity を超えない範囲で、価値の合計を最大にすることです。
ナップサック問題の基本ルール
今回使うルールを、もう少しゲームっぽく並べるとこうなります。
| ルール | 内容 |
|---|---|
| 品物には重さがある | バッグの容量を超えると失敗 |
| 品物には価値がある | 価値の合計をできるだけ大きくしたい |
| 各品物は1回だけ | 同じ品物を何度も選べない |
| 答えは1つとは限らない | 同じ最大価値になる選び方が複数あることもある |
この「答えが1つとは限らない」というところが、ちょっとパズルらしい部分です。
今回の例では、AとCを選ぶと重さは 2 + 3 = 5、価値は 3 + 4 = 7 になります。
また、A、B、Dを選んでも重さは 2 + 1 + 2 = 5、価値は 3 + 2 + 2 = 7 です。
どちらも容量ぴったりで、価値は 7。つまり、最大価値になる選び方が複数あります。
その1：まずは全部試してみるナップサック（全探索）
まずは一番わかりやすい方法から見てみましょう。
品物が4個なら、それぞれについて「選ぶ」「選ばない」の2通りがあります。つまり、全部で 2 * 2 * 2 * 2 = 16 通りです。
16通りくらいなら、全部試してしまえば答えが出ます。
まず、knapsack_bruteforce.py というファイルを作りますが、その前に中心になる関数を見ていきます。
def knapsack_bruteforce(weights, values, capacity):
n = len(weights)
best = 0
for mask in range(1 << n):
total_weight = 0
total_value = 0
for i in range(n):
if mask & (1 << i):
total_weight += weights[i]
total_value += values[i]
if total_weight <= capacity:
best = max(best, total_value)
return bestこのコードは、まだ関数を定義しただけです。実際のデータを渡して実行する前に、中で何をしているのかを順番に見ていきます。
このコードのパズル要素
このコードの肝は ビットで選び方を表す ところです。
for mask in range(1 << n):1 << n は、2^n と同じ意味です。品物が4個なら 16 なので、mask は 0 から 15 まで動きます。
2^nは、2 の n 乗という意味になります。
たとえば、mask を2進数で見ると、各ビットを「品物を選ぶかどうか」に対応させることができます。
| mask | 2進数 | 選び方のイメージ |
|---|---|---|
| 0 | 0000 | 何も選ばない |
| 1 | 0001 | Aだけ選ぶ |
| 3 | 0011 | AとBを選ぶ |
| 5 | 0101 | AとCを選ぶ |
| 15 | 1111 | 全部選ぶ |
このように、数字をひとつ進めるだけで、選び方のパターンを全部なめることができます。
関数の動きが分かったところで、最終的なコードを作ります。knapsack_bruteforce.py に次の内容を保存してください。
def knapsack_bruteforce(weights, values, capacity):
n = len(weights)
best = 0
for mask in range(1 << n):
total_weight = 0
total_value = 0
for i in range(n):
if mask & (1 << i):
total_weight += weights[i]
total_value += values[i]
if total_weight <= capacity:
best = max(best, total_value)
return best
weights = [2, 1, 3, 2]
values = [3, 2, 4, 2]
capacity = 5
print(knapsack_bruteforce(weights, values, capacity))保存できたら、ターミナルで実行します。
python knapsack_bruteforce.py出力はこうなります。
7その2：全探索の限界を見てみる
全探索は素直で、しかも正しい答えを出してくれます。
ただし、品物の数が増えると、試す組み合わせが急に増えていきます。
| 品物数 N | 組み合わせ数 |
|---|---|
| 10 | 1,024 |
| 20 | 1,048,576 |
| 30 | 1,073,741,824 |
N = 30 になると、10億通り以上です。
「全部試せばいいじゃないか」という考え方は、品物が少ないうちは気持ちよく動きます。でも数が増えた瞬間に、急に現実的ではなくなります。
そこで登場するのが、動的計画法（DP） です。
その3：表を埋めていくナップサック（2次元DP）
動的計画法という名前は少し堅いですが、ナップサック問題では 表を少しずつ埋めていく方法 だと考えると分かりやすいです。
ここでは、knapsack_dp.py というファイルを作りますが、その前にまず考え方から見ていきます。
今回使う表は、次の意味を持ちます。
dp[i][w] = 最初の i 個の品物だけを使い、容量 w 以下で得られる最大価値i は「何個目の品物まで見たか」、w は「使える容量」です。
品物を1つ見るたびに、考えることは2つだけです。
- その品物を選ばない
- その品物を選ぶ
品物を選ばない場合は、価値は前の状態のままです。
dp[i + 1][w] = dp[i][w]品物を選ぶ場合は、その品物の重さだけ容量を使い、価値を足します。
dp[i + 1][w] = dp[i][w - weights[i]] + values[i]この2つを比べて、大きい方を採用します。
この考え方を関数にすると、次のようになります。
def knapsack_dp(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(n):
for w in range(capacity + 1):
dp[i + 1][w] = dp[i][w]
if w >= weights[i]:
dp[i + 1][w] = max(
dp[i + 1][w],
dp[i][w - weights[i]] + values[i],
)
return dp[n][capacity]このコードのパズル要素
全探索では、選び方そのものを全部試していました。
一方でDPでは、途中まで見たときのベストな答え を表に保存しておきます。
| 要素 | 意味 |
|---|---|
i | 最初の i 個の品物を使う |
w | 容量 w まで使える |
dp[i][w] | その条件で得られる最大価値 |
たとえば、dp[2][3] は「最初の2個の品物だけを使い、容量3以内で得られる最大価値」です。
つまり、毎回ゼロから考え直すのではなく、「ここまでなら答えはもう分かっている」という小さな結果を再利用しているわけです。
関数の動きが分かったところで、最終的なコードを作ります。knapsack_dp.py に次の内容を保存してください。
def knapsack_dp(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(n):
for w in range(capacity + 1):
dp[i + 1][w] = dp[i][w]
if w >= weights[i]:
dp[i + 1][w] = max(
dp[i + 1][w],
dp[i][w - weights[i]] + values[i],
)
return dp[n][capacity]
weights = [2, 1, 3, 2]
values = [3, 2, 4, 2]
capacity = 5
print(knapsack_dp(weights, values, capacity))保存できたら、ターミナルで実行します。
python knapsack_dp.py出力は全探索と同じです。
7その4：選んだ品物を後ろからたどる
ここまでのコードでは、最大価値だけが分かります。
でも実際には、「どの品物を選んだのか」も知りたくなります。その場合は、完成したDPテーブルを後ろからたどります。
ここでは、knapsack_with_items.py というファイルを作りますが、まず関数の中身を見ていきます。
def knapsack_with_items(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(n):
for w in range(capacity + 1):
dp[i + 1][w] = dp[i][w]
if w >= weights[i]:
dp[i + 1][w] = max(
dp[i + 1][w],
dp[i][w - weights[i]] + values[i],
)
selected = []
w = capacity
for i in range(n - 1, -1, -1):
if dp[i + 1][w] != dp[i][w]:
selected.append(i)
w -= weights[i]
selected.reverse()
return dp[n][capacity], selectedこのコードのパズル要素
復元では、表を最後から逆向きに見ます。
if dp[i + 1][w] != dp[i][w]:この行は、「品物 i を見たあとで価値が変わったか？」を調べています。
価値が変わっているなら、その品物を選んだということです。選んだら、その品物の重さぶんだけ容量を戻します。
w -= weights[i]ゴールからスタートへ戻っていくように、選んだ品物をたどるのが面白いところです。
関数の動きが分かったところで、最終的なコードを作ります。knapsack_with_items.py に次の内容を保存してください。
def knapsack_with_items(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(n):
for w in range(capacity + 1):
dp[i + 1][w] = dp[i][w]
if w >= weights[i]:
dp[i + 1][w] = max(
dp[i + 1][w],
dp[i][w - weights[i]] + values[i],
)
selected = []
w = capacity
for i in range(n - 1, -1, -1):
if dp[i + 1][w] != dp[i][w]:
selected.append(i)
w -= weights[i]
selected.reverse()
return dp[n][capacity], selected
weights = [2, 1, 3, 2]
values = [3, 2, 4, 2]
capacity = 5
best_value, selected = knapsack_with_items(weights, values, capacity)
print(best_value)
print(selected)保存できたら、ターミナルで実行します。
python knapsack_with_items.py出力例です。
7
[0, 2][0, 2] は、0番目と2番目の品物を選んだという意味です。
今回のリストでは、0番目がA、2番目がCです。つまり、重さは 2 + 3 = 5、価値は 3 + 4 = 7 になります。
その5：1次元の表で省メモリ化する
2次元DPは考え方が見えやすい一方で、(品物数 + 1) * (容量 + 1) のメモリを使います。
最大価値だけを求めたい場合は、1次元のリストでも実装できます。
ここでは、knapsack_dp_1d.py というファイルを作りますが、その前にまず関数の中身を見ていきます。
def knapsack_dp_1d(weights, values, capacity):
dp = [0] * (capacity + 1)
for weight, value in zip(weights, values):
for w in range(capacity, weight - 1, -1):
dp[w] = max(dp[w], dp[w - weight] + value)
return dp[capacity]このコードのパズル要素
1次元DPで一番大事なのは、容量 w を大きい方から小さい方へ更新することです。
for w in range(capacity, weight - 1, -1):小さい方から更新してしまうと、今見ている品物を同じ周回の中で何度も使ったような結果になることがあります。
0/1ナップサック問題では、各品物は1回しか選べません。そのため、1つ前の状態を壊さないように、後ろから更新します。
ここは、ナップサック問題の中でもかなりパズルらしいポイントです。
関数の動きが分かったところで、最終的なコードを作ります。knapsack_dp_1d.py に次の内容を保存してください。
def knapsack_dp_1d(weights, values, capacity):
dp = [0] * (capacity + 1)
for weight, value in zip(weights, values):
for w in range(capacity, weight - 1, -1):
dp[w] = max(dp[w], dp[w - weight] + value)
return dp[capacity]
weights = [2, 1, 3, 2]
values = [3, 2, 4, 2]
capacity = 5
print(knapsack_dp_1d(weights, values, capacity))保存できたら、ターミナルで実行します。
python knapsack_dp_1d.py出力はこうなります。
7計算量を比べてみる
最後に、それぞれの方法の計算量を比べてみます。
| 方法 | 時間計算量 | 空間計算量 |
|---|---|---|
| 全探索 | O(2^N) | O(1) |
| 2次元DP | O(NW) | O(NW) |
| 1次元DP | O(NW) | O(W) |
ここで、N は品物数、W はナップサックの容量です。
全探索は「全部試す」ので分かりやすいですが、品物数が増えると一気に重くなります。
DPは「品物をどこまで見たか」と「容量がいくつか」という状態だけを管理するため、全探索よりずっと効率よく答えを求められます。
まとめ
今回は、Pythonで0/1ナップサック問題をコードパズルとして見てみました。
- ナップサック問題は、容量以内で価値の合計を最大化する問題
- 0/1ナップサックでは、各品物を「選ぶ」か「選ばない」かで考える
- 全探索では、ビットを使ってすべての選び方を試せる
- 動的計画法では、
dp[i][w]という表に小さな答えを保存する - 選んだ品物は、完成したDPテーブルを後ろからたどると復元できる
- 1次元DPでは、容量を大きい方から小さい方へ更新するのがポイント
ナップサック問題は、最初は少しとっつきにくく見えます。
でも、「入れるか、入れないか」を順番に考える小さなパズルとして見ると、全探索からDPへの流れがかなり分かりやすくなります。
まずは2次元DPで表の意味をつかみ、そのあとで1次元DPの省メモリ版に進むと、動的計画法の考え方を無理なく追えると思います。
Pythonを学んだ後にゲーム開発へ進みたい人向けのスクール
用途ごとに選ぶ Pythonのおすすめ本
