[Python] 動的計画法 ナップザック問題

#AOJ Knapsack Problem

#個数制限なしのナップサック問題
価値が $v_i$ 重さが $w_i$ であるような $N$ 種類の品物と、容量が $W$ のナップザックがあります。

次の条件を満たすように、品物を選んでナップザックに入れます：

最適化問題に適用する場合、一般的に、以下の2つが適用する問題に成立していないといけない:

• 選んだ品物の価値の合計をできるだけ高くする。
• 選んだ品物の重さの総和は $W$ を超えない。
• 同じ種類の品物はいくつでも選ぶことができる。

価値の合計の最大値を求めてください。

#問題の解法

動的計画法による外部設計は次のようになります。

$dp[i+1][j]$の定義：
$i$ 問目までの品物から重さの総和が$j$以下となるように選んだときの、価値の総和の最大値とする。

dp初期条件：

dp[0][j]=1

dp漸化式の定義：

dp[i+1][j]=max\{dp[i][j-k×w[i]]+k×v[i] \}

これだと三重ループになってしまうため、計算量は $O(nW^2)$ となり、タイムオーバーです。漸化式の式変形を行うことで $k$ のループをなくすことができ、計算量を $O(nW)$ とすることができます。この変形は情報処理における重複計算を省く目的です。理解の仕方としては、$dp[i+1][j]$ を求めるには一段手前の $dp[i][*]$ からではなく、$dp[i][j]$ と $dp[i+1][j-w[i]]+v[i]$ を見れば十分ということであり、逆にループを回すということでもあります。蟻本の解説が分かり易いです。

dp漸化式の変形：

dp[i+1][j]=max(dp[i][j], dp[i+1][j-w[i]]+v[i])

求める解：$dp[n][W]$

サンプルコード

n = int(input())
w = []
v = []
for i in range(n):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)
W = int(input())

dp = [[0] * (W + 1) for i in range(n + 1)]

for i in range(n):
    for j in range(W + 1):
        if j < w[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i])

print(dp[n][W])