【ナップサック問題で遊ぼう】Pythonで全探索から動的計画法まで｜定番問題をコードパズルにしてみた | UNIX Cafe

アルゴリズムを学んでいると、よく登場する定番問題に 「ナップサック問題」 があります。

名前だけ聞くと少し難しそうですが、やっていることはとても身近です。重さと価値の違う品物がいくつかあり、ナップサックに入れられる重さには上限があります。その中で、できるだけ価値が高くなるように品物を選ぶ、という小さなパズルです。

今回は、このナップサック問題を Python で遊びながら見ていきます。最初は全部の選び方を試す素直な方法から始めて、最後は動的計画法（DP）で効率よく解くところまで進みます。

ナップサック問題ってなに？

本題に入る前に、少しだけ 0/1ナップサック問題 のルールを整理しておきます。

たとえば、次のような品物があるとします。

ナップサックの容量は 5 です。

このとき、合計の重さが 5 以下になるように品物を選び、その中で価値の合計を最大にします。

• Aを入れる？ 入れない？
• Bを入れる？ 入れない？
• Cを入れる？ 入れない？
• Dを入れる？ 入れない？

ひとつひとつの品物について「選ぶ」か「選ばない」かを決めるので、これは 0/1ナップサック問題 と呼ばれます。同じ品物を何度も入れることはできません。

Pythonでは、重さと価値をリストで表せます。

weights = [2, 1, 3, 2]
values = [3, 2, 4, 2]
capacity = 5
n = len(weights)

weights = [2, 1, 3, 2]
values = [3, 2, 4, 2]
capacity = 5
n = len(weights)

目標は、capacity を超えない範囲で、価値の合計を最大にすることです。

ナップサック問題の基本ルール

今回使うルールを、もう少しゲームっぽく並べるとこうなります。

今回の例では、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 and total_value > best:
            best = total_value

    return best

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 and total_value > best:
            best = total_value

    return best

このコードは、すべての選び方をビットで表して調べています。

関数の引数

def knapsack_bruteforce(weights, values, capacity):

def knapsack_bruteforce(weights, values, capacity):

• weights: 各品物の重さ
• values: 各品物の価値
• capacity: ナップサックに入れられる最大重量

Pythonのリストは len(weights) で要素数を調べられます。そのため、品物の数 n は関数の中で求めています。

ビットで選び方を表す

for mask in range(1 << n):

for mask in range(1 << n):

1 << n は、2 の n 乗を意味します。

品物が n 個あるとき、それぞれの品物について「入れる / 入れない」の2通りがあるので、組み合わせは全部で 2^n 通りあります。

品物が4個なら 16 通りなので、mask は 0 から 15 まで動きます。

各ビットが 1 ならその品物を選び、0 なら選ばない、と考えます。

if mask & (1 << i):
    total_weight += weights[i]
    total_value += values[i]

if mask & (1 << i):
    total_weight += weights[i]
    total_value += values[i]

mask & (1 << i) は、i 番目のビットが立っているかどうかを調べています。立っていれば、その品物を選んでいるという意味です。

全探索版の完成コード

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 and total_value > best:
            best = total_value

    return best


weights = [2, 1, 3, 2]
values = [3, 2, 4, 2]
capacity = 5

answer = knapsack_bruteforce(weights, values, capacity)
print(f"最大価値: {answer}")

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 and total_value > best:
            best = total_value

    return best


weights = [2, 1, 3, 2]
values = [3, 2, 4, 2]
capacity = 5

answer = knapsack_bruteforce(weights, values, capacity)
print(f"最大価値: {answer}")

実行すると、最大価値は 7 になります。

python3 knapsack_bruteforce.py

python3 knapsack_bruteforce.py

最大価値: 7

最大価値: 7

全探索の弱点

全探索は考え方がとても素直です。ただし、品物の数が増えると組み合わせの数が急激に増えます。

品物が30個になると、10億通り以上を調べることになります。ここから先は、もう少し賢い方法がほしくなります。

その2：動的計画法（DP）で解く

次に、ナップサック問題の定番解法である 動的計画法（DP） を使います。

DPでは、「ここまでの品物を見たとき、容量がこの重さなら、最大価値はいくつか」という小さな答えを表に保存していきます。

たとえば、dp[i][w] を次のように考えます。

i 個目までの品物を見て、容量 w まで使えるときの最大価値

品物を1つずつ見ながら、「この品物を入れない場合」と「この品物を入れる場合」を比べます。

DPの更新ルール

品物 i の重さを weights[i - 1]、価値を values[i - 1] とすると、次のように更新できます。

dp[i][w] = dp[i - 1][w]

dp[i][w] = dp[i - 1][w]

これは「品物 i を入れない」場合です。前の行の答えをそのまま使います。

if w >= weights[i - 1]:
    candidate = dp[i - 1][w - weights[i - 1]] + values[i - 1]
    dp[i][w] = max(dp[i][w], candidate)

if w >= weights[i - 1]:
    candidate = dp[i - 1][w - weights[i - 1]] + values[i - 1]
    dp[i][w] = max(dp[i][w], candidate)

これは「品物 i を入れる」場合です。入れられる重さが残っているなら、入れたときの価値を計算し、より大きいほうを採用します。

DP版の完成コード

Pythonでは、リスト内包表記を使うと2次元のDP表を作りやすいです。

def knapsack_dp(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]

            if w >= weights[i - 1]:
                candidate = dp[i - 1][w - weights[i - 1]] + values[i - 1]
                dp[i][w] = max(dp[i][w], candidate)

    return dp[n][capacity]


weights = [2, 1, 3, 2]
values = [3, 2, 4, 2]
capacity = 5

answer = knapsack_dp(weights, values, capacity)
print(f"最大価値: {answer}")

def knapsack_dp(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]

            if w >= weights[i - 1]:
                candidate = dp[i - 1][w - weights[i - 1]] + values[i - 1]
                dp[i][w] = max(dp[i][w], candidate)

    return dp[n][capacity]


weights = [2, 1, 3, 2]
values = [3, 2, 4, 2]
capacity = 5

answer = knapsack_dp(weights, values, capacity)
print(f"最大価値: {answer}")

実行結果は、全探索と同じく 7 です。

python3 knapsack_dp.py

python3 knapsack_dp.py

最大価値: 7

最大価値: 7

その3：1次元DPでメモリを節約する

さきほどのDPは、dp[n + 1][capacity + 1] という2次元の表を使いました。考え方はわかりやすいのですが、容量が大きくなるとメモリをたくさん使います。

実は、0/1ナップサック問題では dp[w] だけを持つ1次元DPにもできます。

for i in range(n):
    for w in range(capacity, weights[i] - 1, -1):
        dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

for i in range(n):
    for w in range(capacity, weights[i] - 1, -1):
        dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

ここで大事なのは、w を大きいほうから小さいほうへ動かすことです。

小さいほうから更新してしまうと、同じ品物を同じ回の中で何度も使ったような状態になります。0/1ナップサックでは各品物は1回だけなので、後ろから更新します。

1次元DP版の完成コード

def knapsack_dp_1d(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[capacity]


weights = [2, 1, 3, 2]
values = [3, 2, 4, 2]
capacity = 5

answer = knapsack_dp_1d(weights, values, capacity)
print(f"最大価値: {answer}")

def knapsack_dp_1d(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[capacity]


weights = [2, 1, 3, 2]
values = [3, 2, 4, 2]
capacity = 5

answer = knapsack_dp_1d(weights, values, capacity)
print(f"最大価値: {answer}")

こちらも答えは 7 です。

python3 knapsack_dp_1d.py

python3 knapsack_dp_1d.py

最大価値: 7

最大価値: 7

全探索とDPの違い

最後に、全探索とDPの違いを整理しておきます。

DPは、容量 capacity が大きすぎる場合には注意が必要ですが、全探索よりずっと現実的に使える場面が多いです。

Pythonで書くときの注意点

• リストの要素数は len(weights) で調べられる
• 1 << n を使う全探索は、n が大きいと実行時間が急に増える
• 2次元DPのリストは大きくなりやすいので、容量が大きいときは1次元DPも検討する
• 1次元DPでは、容量 w を後ろから更新することが重要

まとめ

ナップサック問題は、アルゴリズムの考え方がぎゅっと詰まった定番問題です。

• 全探索では、すべての選び方をビットで表して試せる
• 品物が増えると、全探索は急に重くなる
• DPを使うと、同じような計算を表に保存して効率よく解ける
• Pythonではリストを使って、DPの表や配列を短く書ける

最初は全探索で「全部試す」感覚をつかみ、そのあとDPで「前に計算した答えを使い回す」感覚に進むと、ナップサック問題はかなり理解しやすくなります。

C言語で学ぶナップサック問題

C言語で配列やビット演算を使って解きたい場合は、こちらの記事も参考にしてください。