网站设计制作公司需要什么资质,网站关键字排名怎么做,百度推广 个人网站,如何让搜索引擎收录你的网站01背包#xff08;滚动数组方法#xff09;
学习资料#xff1a;代码随想录 (programmercarl.com)
题目链接#xff08;和上次一样#xff09;#xff1a;题目页面 (kamacoder.com)
思路
使用一维滚动数组代替二维数组。二维数组的解法记录在#xff1a;代码随想录算…01背包滚动数组方法
学习资料代码随想录 (programmercarl.com)
题目链接和上次一样题目页面 (kamacoder.com)
思路
使用一维滚动数组代替二维数组。二维数组的解法记录在代码随想录算法训练营第四十五天动态规划篇|01背包-CSDN博客
1. dp[j]定义
容量为j的背包可以背的物品的最大价值。
2. 递推公式
dp[j] max(dp[j], dp[j - weight[i]] value[i])
3. 初始条件
dp[0] 0, 根据递推公式dp[j]取当前和前面的值的最大值题目给的价值都是正整数那么非0下标都初始化为0就可以了。
4. 遍历顺序
先遍历物品再从大到小遍历背包。之所以要从大到小遍历是为了防止物品被重复放入。
e.g. i 0: dp[1] 15, dp[2] max(dp[2] 0, dp[2-weight[1]] value[1] dp[1] value[1] 15 15 30)。 而当从后往前遍历时 i 0: dp[4] 15 dp[3] max(0, dp[2] value[0]) max(0, 0 15) 15是正确的。
二维数组可以从小到大遍历是因为当前的dp[i][j]不包括当前的物品i是从[0, i-1]中选取物品。
5. 举例推导dp数组 代码实现
objNum, bagWeightmap(int,input().split())weight [int(i) for i in input().split()]
value [int(i) for i in input().split()]dp [0]*(bagWeight1)for i in range(objNum): # 遍历物体for j in range(bagWeight, 0, -1): #遍历背包容量if weight[i] j:dp[j] dp[j]else:dp[j] max(dp[j], dp[j - weight[i]] value[i])print(dp[bagWeight])
