ナップサック問題（動的計画法）

動的計画法

今回は 動的計画法 を使ってナップサック問題を解いていきます。

動的計画法 は、値を覚えて再利用する手法です。

[問題]

Ｎ個の品物があります。

それぞれの品物の 重さ(weight) と 価値(value) は分かっています。

これらの品物からいくつか選んでナップサックに詰めていきます。

ナップサックにい列品物の総和は capacity を超えてはいけません。

選んだ品物の価値の総和として考えられる最大値を求めて下さい。

前回使った メモ化した辞書型データ に注目してみます。

メモ化した辞書型データ は、ｉ番目以降の品物から、重さの総和がｊ以下 となるように選んだ時の 価値の総和の最大値 となっています。

再帰関数を書かなくても、直接この 漸化式 を用いて各項目の値を順に計算していくことにより、単純な二重ループ で ナップサック問題を解くことができます。

（漸化式 とは、数列の各項をその前の頃から1通りに定める規則を表す等式のことです。）

解法・ソースコード

前回の 再帰関数 をもとに、動的計画法 で実装を行うと下記のようになります。

２重ループの中で、漸化式 を使って順番に メモ化テーブル に結果を格納していきます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
# メモ化テーブル
dp = {}
for i in range(len(items) - 1, -1, -1):     # アイテムを後ろからループ
    for j in range(capacity + 1):
        if j < items[i]['weight']:          # 重さが許容範囲外の場合
            dp[i, j] = dp.get((i + 1, j), 0)
        else:                               # 重さが許容範囲内の場合
            # 品物を入れない場合
            a = dp.get((i + 1, j), 0)
            # 品物を入れる場合（許容範囲の重さを減らし、価値を増やす）
            b = dp.get((i + 1, j - items[i]['weight']), 0) + items[i]['value']
            dp[i, j] = max(a, b)    # 価値が高いほうを選択

print('解：', dp[0, 5])

[実行結果]

解： 7

解（価値の総和の最大値）はこれまで同様 7 となりました。