Pythonで容量制限内に収まる品物の最大価値を求める方法（ナップサック問題の解法）

問題の概要

同じ長さを持つ2つのリスト「weights（重さ）」と「values（価値）」、そして容量を表す数値 k が与えられているとします。weights[i] と values[i] は、それぞれ i 番目の品物の重さと価値を表します。ここで、合計の重さが容量 k を超えない範囲で品物を選びます。ただし、各品物は1つしか選べないものとします。この条件のもとで、取得できる価値の合計の最大値を求めるのが目的です。

これは動的計画法（DP）を使って解ける、いわゆる「0/1 ナップサック問題」の典型例です。

入力例

• weights = [2, 3, 4]
• values = [2, 6, 4]
• capacity = 6

この場合、出力は 8 になります。重さ3の品物（価値6）と重さ2の品物（価値2）を選ぶと、合計重さが5で容量6以内に収まり、価値の合計は8となるためです。

解法のアプローチ

この問題は、二次元のDPテーブルを作成して解きます。手順は以下の通りです。

1. n := weights の要素数とする
2. dp := (n+1) × (capacity+1) のサイズの行列を作成し、すべて0で初期化する
3. i を 0 から n まで繰り返す：
   • j を 0 から capacity まで繰り返す：
     • i が 0 または j が 0 の場合：dp[i][j] := 0
     • weights[i-1] <= j の場合：dp[i][j] = max(dp[i-1][j-weights[i-1]] + values[i-1], dp[i-1][j])
     • それ以外の場合：dp[i][j] := dp[i-1][j]
4. 最後に dp[n][capacity] を返す

dp[i][j] は「i 番目までの品物の中から選び、容量 j 以内で実現できる最大価値」を意味します。品物 i を選ぶ場合と選ばない場合の価値を比較し、大きい方を採用することで最適解を構築していきます。

Pythonでの実装例

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

class Solution:
    def solve(self, weights, values, capacity):
        n = len(weights)
        dp = [[0 for i in range(capacity + 1)]
              for _ in range(n + 1)]
        for i in range(n + 1):
            for j in range(capacity + 1):
                if i == 0 or j == 0:
                    dp[i][j] = 0
                elif weights[i - 1] <= j:
                    dp[i][j] = max(dp[i - 1][j - weights[i - 1]] + values[i - 1], dp[i - 1][j])
                else:
                    dp[i][j] = dp[i - 1][j]
        return dp[n][capacity]

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

入力

[2, 3, 4], [2, 6, 4], 6

出力

8

計算量について

このアルゴリズムの時間計算量は O(n × capacity)、空間計算量も同様に O(n × capacity) となります。品物の数や容量が大きくなると計算量が増加しますが、各品物を1回ずつしか使えない制約がある場合には、この動的計画法による解法が最も確実で標準的なアプローチです。