search

hxrxchang / atcoder

https://atcoder.jp/users/hxrxchang
0 stars 0 forks source link

D - Knapsack 1 #34

Open hxrxchang opened 4 months ago

hxrxchang commented 4 months ago

https://atcoder.jp/contests/dp/tasks/dp_d

2次元テーブルを埋めるのではなく、状態変化の際に依存するのは直前の状態だけなので、dpを1次元にできた。

N, W = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

dp = [-1] * (W + 1)
dp[0] = 0

for w, v in items:
    tmp = dp[:]
    for weight in range(1, W + 1):
        if w <= weight:
            tmp[weight] = max(dp[weight], dp[weight - w] + v)
    dp = tmp

print(max(dp))

https://atcoder.jp/contests/dp/submissions/52950007