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

問題

$ N $ 個の品物があり、それぞれ $ 1 $ から $ N $ までの番号が付けれらています。

品物 $ i $ の重さは整数値 $ w_i $ であり、価値は整数値 $ v_i $ です。

いくつかの品物を選んで持ち帰りたいのですが、品物を入れるナップサックには容量制限があり、重さの合計が $ W $ 以下になるようにする必要があります。

価値の合計としてあり得る最大値はいくらになるでしょうか。

[制約]
🔹$ 1 \leqq N \leqq 100 $
🔹$ 1 \leqq W_i \leqq 100000 $
🔹$ 1 \leqq w_i \leqq W $
🔹$ 1 \leqq v_i \leqq 10^9 $

解き方・ソースコード

この問題は次の二次元配列に対して、動的計画法を適用して解くことができます。

🔹$ dp[i][j] $ ：品物１，２，…，$ N $ の中から、重さの合計が $ j $ となるように選ぶ。
　このとき、合計価値としてあり得る最大値はいくつになるか。

まず、$ i = 0 $の場合は、何も選ぶことができませんので重さや価値の合計は必ず $ 0 $ になります。

$ dp[0][0] = 0 $ とし、他の値については十分に大きなマイナスの値 $ -10^{15} $ を設定しておきます。

次に、$ i \geqq 1 $ の場合は、$ dp[i][j] $ の状態になる方法、つまり品物 $ i $ までの中から重さの合計が $ j $ になるように選ぶ方法として以下の２つだけが考えられます。

🔹方法Ａ：品物 $ i - 1 $ の時点で合計が $ j $ であり、品物 $ i $ を選ばない。
　　　➡　$ dp[i-1][j] $
🔹方法Ｂ：品物 $ i - 1 $ の時点で合計が $ j - w_i $ であり、品物 $ i $ を選ぶ。
　　　➡　$ dp[i-1][j-w_i] + v_i $

つまり $ dp[i][j] $ の値は、$ dp[i-1][j] $ と $ dp[i-1][j-w_i] + v_i $ のうち大きい方を選択します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#--------- 入力例 ----------
N = 4                       # 品物の数
W = 7                       # ナップサックに入れられる最大重量
w = [None, 3,  3,  5,  1]   # 各品物の重さ
v = [None, 13, 17, 29, 10]  # 各品物の価値
#---------------------------
# 動的計画法
dp = [[ -10 ** 15 ] * (W + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):       # 品物ごとにループ
    for j in range(0, W + 1):   # 重さごとにループ
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        if j >= w[i]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

# 出力
print('解：', max(dp[N]))

注意が必要なのは、重さの合計がちょうど $ W $ のとき価値が最大になるとは限らないことです。

求める答えは $ dp[N][0], dp[N][1], …, dp[N][W] $ の最大値となります。

[実行結果]

解： 40

品物１、品物２，品物４を選んだ場合、重さの合計は[3 + 3 + 1 = 7]で価値の合計は[13 + 17 + 10 = 40]となりこれが価値の最大値となります。