ナップサック問題(動的計画法②)

動的計画法(順方向)

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

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

[ナップサック問題]

N個の品物があります。

それぞれの品物の 重さ(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 となっています。