前回と同じナップサック問題を より効率的に解く方法 を考えます。
[問題]
Ｎ個の品物があります。
それぞれの品物の 重さ(weight) と 価値(value) は分かっています。
これらの品物からいくつか選んでナップサックに詰めていきます。
ナップサックにい列品物の総和は capacity を超えてはいけません。
選んだ品物の価値の総和として考えられる最大値を求めて下さい。
メモ化
前回は、再帰関数 を使ってナップサック問題を解きましたが、再帰関数が 同じ引数で何度もコールされる ことがありました。
このままでは非効率なので、メモ化 という方法で効率的に処理を行ってみます。
メモ化 では、最初の計算時の結果を記憶しておくことで、同じ引数での二度目以降の計算を省略 します。
ソースコード
メモ化 のために、9行目、13～14行目、23行目を追加しています。
[Google Colaboratory]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
items = [{'weight':2, 'value':3},
{'weight':1, 'value':2},
{'weight':3, 'value':4},
{'weight':2, 'value':2}]
capacity = 5
memo = {}
def rec(i, j):
if (i, j) in memo:
return memo[i, j]
if i == len(items):
res = 0
elif j < items[i]['weight']:
res = rec(i + 1, j)
else:
res = max(rec(i + 1, j), rec(i + 1, j - items[i]['weight']) + items[i]['value'])
memo[i, j] = res
return res
print(rec(0, capacity))
|
[実行結果]
7
解（価値の総和の最大値）は前回同様 7 となりました。
今回の入力例では、同じ引数で再帰関数がコールされる回数 が少ないので大幅な効率化はしていませんが、この改良により 解ける問題のサイズを大幅に増やす ことができたことになります。
functools
functools というPythonの標準モジュールを使うと デコレータ を設定するだけで 簡単にメモ化 することができます。（8行目、11行目）
[Google Colaboratory]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
items = [{'weight':2, 'value':3},
{'weight':1, 'value':2},
{'weight':3, 'value':4},
{'weight':2, 'value':2}]
capacity = 5
import functools
@functools.lru_cache(maxsize=None)
def rec(i, j):
if i == len(items):
res = 0
elif j < items[i]['weight']:
res = rec(i + 1, j)
else:
res = max(rec(i + 1, j), rec(i + 1, j - items[i]['weight']) + items[i]['value'])
return res
print(rec(0, capacity))
|
[実行結果]
7
