【Python】各アイテムを何度でも選べるナップサック問題で最大価値を求めるプログラム

問題概要

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

ここで特別なルールとして、各アイテムは何個でも（何度でも）選んでよいものとします。合計の重さが capacity を超えない範囲でアイテムを選ぶとき、得られる価値の合計の最大値を求めるのがこの問題です。これは「無制限ナップサック問題（Unbounded Knapsack Problem）」として知られる古典的な動的計画法の応用例です。

たとえば、次の入力を考えてみましょう。

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

この場合の出力は 11 になります。「重さ2・価値5」のアイテムを2つ（重さ4・価値10）と、「重さ1・価値1」のアイテムを1つ（重さ1・価値1）選ぶことで、合計重さちょうど5で価値11を達成できます。

解法のアプローチ

この問題は、再帰的な動的計画法（DP）を使って解くことができます。基本的な考え方は以下の通りです。

1. dp(i, k) 関数を定義します。 引数 i は現在注目しているアイテムのインデックス、k は残りの容量を表します。
2. i が weights の長さと一致したら、これ以上選べるアイテムがないため 0 を返します。
3. まず、現在のアイテムを選ばないケースとして ans = dp(i + 1, k) を計算します。
4. もし k >= weights[i]（容量に余裕がある）なら、アイテムを選ぶケースも評価し、ans = max(ans, dp(i, k - weights[i]) + values[i]) でより大きい方を採用します。
5. ans を返します。
6. メイン処理では dp(0, capacity) の結果を返します。

ここでの重要なポイントは、アイテムを複数回選べるため、再帰呼び出し時にインデックスを i + 1 に進めず、同じ i のまま dp(i, k - weights[i]) を呼び出すことです。これにより「同じアイテムを繰り返し選ぶ」ことが自然に表現されます。

実装例（Pythonコード）

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, weights, values, capacity):
        def dp(i, k):
            if i == len(weights):
                return 0
            ans = dp(i + 1, k)
            if k >= weights[i]:
                ans = max(ans, dp(i, k - weights[i]) + values[i])
            return ans
        return dp(0, capacity)

ob = Solution()
weights = [1, 2, 3]
values = [1, 5, 3]
capacity = 5
print(ob.solve(weights, values, capacity))

入力

[1, 2, 3], [1, 5, 3], 5

出力

11

補足：メモ化による高速化

上記の素朴な再帰実装は、入力が大きくなると同じ状態を何度も計算してしまい、処理時間が爆発的に増える可能性があります。Python標準ライブラリの functools.lru_cache を使ってメモ化を追加すれば、計算量を O(アイテム数 × 容量) まで抑えることができ、実用的な速度になります。

from functools import lru_cache

class Solution:
    def solve(self, weights, values, capacity):
        @lru_cache(maxsize=None)
        def dp(i, k):
            if i == len(weights):
                return 0
            ans = dp(i + 1, k)
            if k >= weights[i]:
                ans = max(ans, dp(i, k - weights[i]) + values[i])
            return ans
        return dp(0, capacity)

まとめ

各アイテムを複数回選べるナップサック問題では、通常の0/1ナップサックとの決定的な違いである「再帰呼び出し後にインデックスを進めない」点を押さえることが鍵となります。再帰的なDPでシンプルに表現でき、メモ化を組み合わせれば大規模な入力にも対応できる、覚えておくと非常に有用なアルゴリズムパターンです。