代码随想录 -- 动态规划 -- 01背包理论基础（滚动数组）

46. 携带研究材料（第六期模拟笔试）

思路：

• dp[j]含义：容量为j的背包的最大价值。

递推公式：

• 如果放不下第i个物品：dp[j]=dp[j]；
• 如果能放得下第i个物品：dp[j]=max(dp[j],dp[j-weight[i]]+value[i])

初始化：

• 全部初始化为0

遍历顺序：

• 先遍历物品，再遍历背包；（如果先遍历背包再遍历物品，背包里只有一个物品了）
• 遍历物品时：从前往后；
• 遍历背包时：从后往前。（保证每个物品只使用一次）

count,bWeight=map(int,input().split())
weight=list(map(int,input().split()))
value=list(map(int,input().split()))
dp=[0]*(bWeight+1)
for i in range(count):for j in range(bWeight,-1,-1):if j-weight[i]>=0 and j-weight[i]<bWeight:dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
print(dp[bWeight])