AOJ Course ナップザック問題

自分のやりたいことは自分がやらないといけない。えぬわいです。

qiita.com

続きです。

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

個数制限なしナップサック問題！

再帰関数書いてDPに直すの慣れてきた！！！ﾔｯﾀｰ

DPを観察して、計算量を落とすタイプの問題。蟻本にも書いてあるやつです。

あるDPのマスを更新するときに、過去の行全てのマスにアクセスする必要はないということに気付けるかが鍵になりそうだと思いました。

以下、コード。

# import sys
# sys.setrecursionlimit(100000)
N, W = map(int, input().split())
v = []; w = []

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

"""
def rec(pos, rest):
    if pos == N:
        return 0
    ans = 0
    for i in range(0, rest//w[pos]+1):
        ans = max(ans, rec(pos+1, rest-w[pos]*i)+v[pos]*i)
    return ans

print(rec(0, W))
"""

dp = [[0 for j in range(W+1)] for i in range(N+1)]

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

おっしゃー、今日も書けたぞ！！