题解 | #【模板】01背包#

记录自己用 Python 写的 0-1 背包模板题

from math import inf
while True:
    try:
        n, V = map(int, input().split(sep=' '))
        v = []
        w = []
        for i in range(n):
            data = list(map(int, input().split(sep=' ')))
            v.append(data[0])
            w.append(data[1])
        
        dp1 = [0] * (V + 1)
        dp2 = [0] + [-inf] * V
        for i in range(n):
            for c in range(V, v[i] - 1, -1):
                dp1[c] = max(dp1[c], dp1[c - v[i]] + w[i])
                dp2[c] = max(dp2[c], dp2[c - v[i]] + w[i])                

        print(dp1[-1])
        print(dp2[-1] if dp2[-1] != -inf else 0)
    except:
        break