E - Knapsack 2

[hxrxchang]

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

https://atcoder.jp/contests/dp/tasks/dp_d との違いは制約が w が 10 9, v が 10 3 になるので、 ある個数までのitemの組み合わせで重さがwとなるときの価値の最大値 ではなく ある個数までのitemの組み合わせで価値がvとなるときの重さの最小値 を求めればok。 重さの最小値がW以下で最大のvが分かれば答えになる。

N, W = map(int, input().split())
items = []
total_v = 0
for _ in range(N):
    w, v = map(int, input().split())
    items.append((w, v))
    total_v += v

dp = [float('inf')] * (total_v + 1)
dp[0] = 0

for w, v in items:
    tmp = dp[:]
    for v2 in range(1, total_v + 1):
        if v2 - v >= 0:
            tmp[v2] = min(dp[v2], dp[v2 - v] + w)
    dp = tmp

ans = 0
for i, weight in enumerate(dp):
    if weight <= W:
        ans = i

print(ans)

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