代码随想录 -- 动态规划 -- 完全背包理论基础

52. 携带研究材料（第七期模拟笔试）

思路：

dp[j]的含义：

• 装满容量为j的背包时，背包的最大价值为dp[j].

递推公式：

• 当j>=weight[i]时：dp[j]=max(dp[j],dp[j-weight[i]]+value[i])

初始化：

• 全部初始化为0

遍历顺序：

• 先遍历物品和先遍历背包都可以，都是从前往后遍历（因为物品可以重复使用）。

n,v=map(int,input().split())
weight=[0]*n
value=[0]*n
for i in range(n):
    weight[i],value[i]=map(int,input().split())
# print(weight,value)
dp=[0]*(v+1)
for i in range(n):
    for j in range(weight[i],v+1):
        dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
print(dp[v])