题解 | 【模板】01背包

n, v = map(int,input().split())
goods = [list(map(int,input().split())) for _ in range(n)]
# --- 方案一：不要求装满 ---
dp1 = [0]*(v+1)
for u,w in goods:#决定每件物品是否放入背包
    for j in range(v, u-1, -1):
        dp1[j] = max(dp1[j], dp1[j-u]+w)
print(dp1[v])
# --- 方案二：要求恰好装满 ---
INF = -float('inf')
dp2 = [INF]*(v+1)
dp2[0] = 0
for u,w in goods:#决定每件物品是否放入背包
    for j in range(v, u-1, -1):
        if dp2[j-u] != INF:# 确保前一状态是可达的
            dp2[j] = max(dp2[j], dp2[j-u]+w)

if dp2[v] == INF:
    print(0)
else:
    print(dp2[v])