AOJ Course 0-1ナップザック問題

qiita.com

続きです。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp

言わずもしれたナップザック問題。

動的計画法を考察してみる。なあなあだったので。今回は、蟻本を参考にしないで、思い出しながら、書いてみた。

N, M = map(int, input().split())

v = []
w = []

for i in range(N):
    vv, mm = map(int, input().split())
    v.append(vv); w.append(mm)

def rec(i, vv, ww):
    if i == N:
        return vv
    ans = 0
    # 入れるパターン
    if ww >= w[i]:
        ans = rec(i+1, vv+v[i], ww-w[i])
    # 入れないパターン
    ans = max(ans, rec(i+1, vv, ww))
    return ans

if __name__ == '__main__':
    print(rec(0, 0, M))

はじめに、全探索するコードを書いた。 ここで、

rec(i, vv, ww) = ( i 番目から N-1 番目までの最高の価値)

である。

次に、内部の実装をみる。

rec(i, vv, ww) = max(rec(i+1, vv, ww), rec(i+1, vv+v[i], ww-w[i]))
もしくは、
rec(i, vv, ww) = rec(i+1, vv, ww)

となっている。

ここで、vv がいらないことに気づく。

N, M = map(int, input().split())

v = []
w = []

for i in range(N):
    vv, mm = map(int, input().split())
    v.append(vv); w.append(mm)

# 引数減らす
def rec(i, ww):
    if i == N:
        # ここ変更
        return 0
    ans = 0
    # 入れるパターン
    if ww >= w[i]:
        ans = rec(i+1, ww-w[i]) + v[i]
    # 入れないパターン
    ans = max(ans, rec(i+1, ww))
    return ans

if __name__ == '__main__':
    print(rec(0, M))

こうなる。 すると、

rec(i, ww) = max(rec(i+1, ww), rec(i+1, ww-w[i]) + v[i])
もしくは、
rec(i, ww) = rec(i+1, ww)

こうなる。同じ引数のときは、配列でメモ化することを考えると、

rec[i][ww] = max(rec[i+1][ww], rec[i+1][ww-w[i]]+v[i])
もしくは、
rec[i][ww] = max(rec[i+1][ww])

となる。

ここで、上記の漸化式を見ると、rec[i][ww] を求めるには、少なくとも、rec[i][ww-w[i] が求まる必要がある。ww-w[i] >= 0 のもとでは、下の式が適応されるから、ww が 0 のときも、ww を 0 から更新し、rec[i+1][j] の i の部分は、上から下るように更新していけば、rec[0][M] が求められる。 したがって、

N, M = map(int, input().split())

v = []
w = []

for i in range(N):
    vv, mm = map(int, input().split())
    v.append(vv); w.append(mm)

dp = [[0 for j in range(M+1)] for i in range(N+1)]
for i in range(N-1, -1, -1):
    for j in range(M+1):
        if j-w[i] >= 0:
            dp[i][j] = max(dp[i+1][j-w[i]]+v[i], dp[i+1][j])
        else:
            dp[i][j] = dp[i+1][j]
print(dp[0][M])

となる。

うーん、もうちょっと考察しがいがあると思った。

ここで、発生した疑問として、

どうして自分が、 vv を消せることに気づけたのかがわからない。直感的すぎるし、別の問題でも引数減らせるかわからないなぁ。

この疑問が発生したことによって、再帰関数は、可能な限り引数の個数を小さく実装するよう心がける必要があることがわかった。