福建建设资格管理中心网站,北京新鸿儒做的网站,广西建设网个人查询,公司为什么要建立网站背包问题其实有很多种#xff0c;01背包是最基础也是最经典的#xff0c;软工计科学生一定要掌握的。 01背包问题 代码随想录 视频讲解#xff1a;带你学透0-1背包问题#xff01;| 关于背包问题#xff0c;你不清楚的地方#xff0c;这里都讲了#xff01;| 动态规划经…背包问题其实有很多种01背包是最基础也是最经典的软工计科学生一定要掌握的。 01背包问题 代码随想录 视频讲解带你学透0-1背包问题| 关于背包问题你不清楚的地方这里都讲了| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili 思路 直接上动态规划五部曲 1、dp数组及其下标的含义 对于背包问题有一种写法 是使用二维数组即dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。 2.确定递推公式 再回顾一下dp[i][j]的含义从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。 那么可以有两个方向推出来dp[i][j] 不放物品i由dp[i - 1][j]推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以背包内的价值依然和前面相同。)放物品i由dp[i - 1][j - weight[i]]推出dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值 所以递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 3.初始化 首先从dp[i][j]的定义出发如果背包容量j为0的话即dp[i][0]无论是选取哪些物品背包价值总和一定为0。 再看其他情况。 状态转移方程 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 可以看出i 是由 i-1 推导出来那么i为0的时候就一定要初始化。 dp[0][j]即i为0存放编号0的物品的时候各个容量的背包所能存放的最大价值。 那么很明显当 j weight[0]的时候dp[0][j] 应该是 0因为背包容量比编号0的物品重量还小。 当j weight[0]时dp[0][j] 应该是value[0]因为背包容量放足够放编号0物品。 4.确定遍历顺序 在如下图中可以看出有两个遍历的维度物品与背包重量 那么问题来了先遍历 物品还是先遍历背包重量呢 其实都可以 但是先遍历物品更好理解。 5.举例验证直接看链接里的吧。 代码
def test_2_wei_bag_problem1():weight [1, 3, 4]value [15, 20, 30]bagweight 4# 二维数组dp [[0] * (bagweight 1) for _ in range(len(weight))]# 初始化for j in range(weight[0], bagweight 1):dp[0][j] value[0]# weight数组的大小就是物品个数for i in range(1, len(weight)): # 遍历物品for j in range(bagweight 1): # 遍历背包容量if j weight[i]:dp[i][j] dp[i - 1][j]else:dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i])print(dp[len(weight) - 1][bagweight])test_2_wei_bag_problem1()01背包滚动数组 代码随想录 视频讲解带你学透01背包问题滚动数组篇 | 从此对背包问题不再迷茫_哔哩哔哩_bilibili 看链接吧老是复制粘贴累了。 416.分割等和子集 本题是 01背包的应用类题目 代码随想录 视频讲解动态规划之背包问题这个包能装满吗| LeetCode416.分割等和子集_哔哩哔哩_bilibili 思路 就是01背包的应用背包的大小是总和的一半遍历每一个物品看看遍历到最后能不能装满这个背包。
代码二维版本在链接里
class Solution:def canPartition(self, nums: List[int]) - bool:if sum(nums) % 2 ! 0:return Falsetarget sum(nums) // 2dp [0] * (target 1)for num in nums:for j in range(target, num-1, -1):dp[j] max(dp[j], dp[j-num] num)return dp[-1] target
