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

問題

N 個の品物があります。 品物には 1,2,…,N と番号が振られています。

各 i (1≦i≦N) について、品物 i の重さは w_i で、価値は v_iです。

N 個の品物のうちいくつかを選び、ナップサックに入れて持ちかえります。 

ナップサックの容量は W であり、持ち帰る品物の重さの総和は W 以下でなければなりません。

持ち帰る品物の価値の総和の最大値を求めてください。

解法・ソースコード

今回は、もっとも単純な ナップサック問題 のおさらいです。

品物ごと、許容範囲の重さごと にループを回して、品物を入れるか入れないかを選択し、価値の高くなる方の選択結果を メモ化テーブル に格納していきます。

[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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#--------- 入力例1 ----------
w = 8
items = [{'weight':3, 'value':30},
         {'weight':4, 'value':50},
         {'weight':5, 'value':60}]
#--------- 入力例2 ----------
# w = 5
# items = [{'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000}]
#--------- 入力例3 ----------
# w = 15
# items = [{'weight':6, 'value':5},
#          {'weight':5, 'value':6},
#          {'weight':6, 'value':4},
#          {'weight':6, 'value':6},
#          {'weight':3, 'value':5},
#          {'weight':7, 'value':2}]
#----------------------------
n = len(items)    # 品物の総数

# メモ化テーブル（動的計画法用）
memo = {}

for i, item in enumerate(items):    # 品物ごとにループ
    for j in range(w + 1):          # 重さ＋1までループ
        if j < items[i]['weight']:          # 重さが許容範囲外の場合
            # 品物を入れない
            memo[i + 1, j] = memo.get((i, j), 0)
        else:                               # 重さが許容範囲内の場合
            # 品物を入れない場合
            a = memo.get((i, j), 0)
            # 品物を入れる場合（許容範囲の重さを減らし、価値を増やす）
            b = memo.get((i, j - items[i]['weight']), 0) + items[i]['value']
            memo[i + 1, j] = max(a, b)    # 価値が高いほうを選択

print('【メモ化テーブルの内容】')
for i, item in enumerate(items):    # 品物ごとにループ
    for j in range(w):              # 重さごとにループ
        print(str(memo[i+1, j+1]).rjust(2, ' '), end=' ')
    print()
print('-----------------------')
print('解（価値の総和の最大値）：', memo[len(items), w])

[実行結果(入力例1)]

【メモ化テーブルの内容】
 0  0 30 30 30 30 30 30 
 0  0 30 50 50 50 80 80 
 0  0 30 50 60 60 80 90 
-----------------------
解（価値の総和の最大値）： 90

品物 1,3 を選ぶと、重さの総和は 3+5=8 となり、価値の総和は 30+60=90 となります。

[実行結果(入力例2)]

【メモ化テーブルの内容】
1000000000 1000000000 1000000000 1000000000 1000000000 
1000000000 2000000000 2000000000 2000000000 2000000000 
1000000000 2000000000 3000000000 3000000000 3000000000 
1000000000 2000000000 3000000000 4000000000 4000000000 
1000000000 2000000000 3000000000 4000000000 5000000000 
-----------------------
解（価値の総和の最大値）： 5000000000

全部の品物 を持っていくことができるので、価値の総和は 5000000000 となります。

[実行結果(入力例3)]

【メモ化テーブルの内容】
 0  0  0  0  0  5  5  5  5  5  5  5  5  5  5 
 0  0  0  0  6  6  6  6  6  6 11 11 11 11 11 
 0  0  0  0  6  6  6  6  6  6 11 11 11 11 11 
 0  0  0  0  6  6  6  6  6  6 12 12 12 12 12 
 0  0  5  5  6  6  6 11 11 11 12 12 12 17 17 
 0  0  5  5  6  6  6 11 11 11 12 12 12 17 17 
-----------------------
解（価値の総和の最大値）： 17

品物 2,4,5 を選ぶと、重さの総和は 5+6+3=14 で価値の総和は 6+6+5=17 となります。