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

動的計画法（順方向）

前回は 動的計画法 を使ってナップサック問題を解きましたが、再帰関数に合わせてループの順番が 逆方向 になっていました。

今回は、このループの順番を 順方向 に変えてみます。

[ナップサック問題]

Ｎ個の品物があります。

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

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

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

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

解法・ソースコード

ループを 順方向 に変えるためには、ループ文 と 漸化式 を少し変更する必要がありますが、根本的な内容は前回記事の処理と変わりません。

[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(0, len(items) ):             # アイテムを順方向にループ
    for j in range(capacity + 1):           # 重さを順番にループ
        if j < items[i]['weight']:          # 重さが許容範囲外の場合
            dp[i + 1, j] = dp.get((i, j), 0)
        else:                               # 重さが許容範囲内の場合
            # 品物を入れない場合
            a = dp.get((i, j), 0)
            # 品物を入れる場合（許容範囲の重さを減らし、価値を増やす）
            b = dp.get((i, j - items[i]['weight']), 0) + items[i]['value']
            dp[i + 1, j] = max(a, b)        # 価値が高いほうを選択

print('解：', dp[len(items), 5])

ループを 順方向 に変えることで、ループ文 や 漸化式 がシンプルで分かりやすくなったのではないでしょうか。

[実行結果]

解： 7

解（価値の総和の最大値）はこれまで同様 7 となっています。