题解 | 【模板】01背包

import sys
from math import inf
n,v = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(n)]
# dp[i][j]定义为装前i个物品在容量为j的情况下的最大价值
# dp[i][0]=0,dp[0][j]=0
# 核心转移关系
# if j < v[i-1]: # 当前容量小于第i个物品的体积
#     dp[i][j] = dp[i-1][j]
# else:
#     not_take = dp[i-1][j]
#     take = dp[i-1][j-v[i-1]]+w[i-1]
#     dp[i][j] = max(not_take,take)

# 不要求装满背包方案
dp1 = [[0]*(v+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,v+1):
        if j < a[i-1][0]:
            dp1[i][j] = dp1[i-1][j]
        else:
            not_take = dp1[i-1][j]
            take = dp1[i-1][j-a[i-1][0]]+a[i-1][1]
            dp1[i][j] = max(not_take,take)
print(dp1[n][v])

# 要求恰好装满背包方案
# dp[i][j]定义为装前i个物品在恰好装满体积为j的背包时的最大价值
# dp[0][0]=0,dp[i][0]=0
# if j != v[i-1]:dp[i][j] = dp[i-1][j]
# else:dp[i][j] = dp[i-1][j-v[i-1]]+w[i-1]
dp2 = [[-inf]*(v+1) for _ in range(n+1)]
dp2[0][0]=0
for i in range(1,n+1):
    dp2[i][0]=0
    for j in range(1,v+1):
        if j < a[i-1][0]:
            dp2[i][j] = dp2[i-1][j]
        else:
            dp2[i][j] = max(dp2[i-1][j-a[i-1][0]]+a[i-1][1],dp2[i-1][j])
if dp2[n][v]==-inf:
    print(0)
else:
    print(dp2[n][v])