Pythonでナップサック問題を解く：容量と個数の制約付きで最大価値を求める方法

この記事では、Pythonを使って「容量」と「個数」の2つの制約を持つナップサック問題（0/1 Knapsack問題の拡張版）を解き、バッグに入れられるアイテムから得られる価値の最大値を求めるプログラムを紹介します。

問題の概要

同じ長さを持つ2つの数値リスト weights（重さ）と values（価値）、そして2つの数値 capacity（許容重量）と count（最大個数）が与えられます。weights[i] と values[i] は、i番目のアイテムの重さと価値を表します。

持ち運べるのは合計で最大 capacity の重さまで、かつ最大 count 個までのアイテムです。また、各アイテムは1つしか選べません。この条件下で、得られる価値の合計の最大値を求めるのが目的です。

例：

• weights = [2, 2, 4, 6]
• values = [15, 15, 20, 35]
• capacity = 8
• count = 3

この場合の出力は 50 になります。最初の3つのアイテムを選ぶと、合計重量が 2 + 2 + 4 = 8 となり、価値は 15 + 15 + 20 = 50 となるためです。

解法のアプローチ：再帰による動的計画法

この問題は、各アイテムについて「選ぶ」か「選ばない」かを再帰的に判定することで解けます。以下の手順に従います。

1. items を、weights と values をペアにしたリストとして作成します。
2. 関数 dp(i, cp, ct) を定義します。ここで i は現在注目しているアイテムのインデックス、cp は残り容量、ct は残りの選択可能個数です。
3. i がアイテム数と等しい、または ct が 0 の場合は、これ以上アイテムを選べないので 0 を返します。
4. 現在のアイテムを (w, v) = items[i] として取り出します。
5. まず、そのアイテムを選ばない場合の結果 ans = dp(i + 1, cp, ct) を計算します。
6. もし残り容量 cp が重さ w 以上であれば、そのアイテムを選ぶ場合の結果 dp(i + 1, cp - w, ct - 1) + v とも比較し、大きい方を ans とします。
7. ans を返します。
8. メイン処理では dp(0, capacity, count) の結果を返します。

実装例

以下が実際のPythonコードです。

class Solution:
    def solve(self, weights, values, capacity, count):
        items = list(zip(weights, values))

        def dp(i, cp, ct):
            if i == len(items) or ct == 0:
                return 0.0
            w, v = items[i]
            ans = dp(i + 1, cp, ct)
            if cp >= w:
                ans = max(ans, dp(i + 1, cp - w, ct - 1) + v)
            return ans

        return int(dp(0, capacity, count))


ob = Solution()
weights = [2, 2, 4, 6]
values = [15, 15, 20, 35]
capacity = 8
count = 3
print(ob.solve(weights, values, capacity, count))

入力

[2, 2, 4, 6], [15, 15, 20, 35], 8, 3

出力

50

パフォーマンス改善のヒント：メモ化の活用

上記の素朴な再帰実装は、アイテム数が増えると計算量が指数関数的に増大する可能性があります。同じ状態 (i, cp, ct) が何度も計算されるため、functools.lru_cache を使ったメモ化を追加すると効率が大幅に向上します。

from functools import lru_cache

class Solution:
    def solve(self, weights, values, capacity, count):
        items = list(zip(weights, values))

        @lru_cache(maxsize=None)
        def dp(i, cp, ct):
            if i == len(items) or ct == 0:
                return 0
            w, v = items[i]
            ans = dp(i + 1, cp, ct)
            if cp >= w:
                ans = max(ans, dp(i + 1, cp - w, ct - 1) + v)
            return ans

        return dp(0, capacity, count)

メモ化により、状態数は高々「アイテム数 × 容量 × 個数」に抑えられ、計算量は O(n × capacity × count) となります。

まとめ

本記事では、重さ・価値・容量・個数という4つの要素を持つナップサック問題を、再帰的な動的計画法で解く方法を解説しました。「各アイテムを選ぶか選ばないか」を全探索しつつ、制約条件を再帰呼び出しの引数として管理するのがポイントです。実務ではメモ化やボトムアップ型のDPテーブルを組み合わせることで、より大規模な入力にも対応できます。