php可以做视频网站有哪些,备案号查询平台,开发文档,wordpress 机械 主题背包问题
常见的背包问题类型#xff08;大厂面试重点掌握01背包和完全背包即可#xff09;题目描述#xff1a;有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品能用*次#xff0c;求解怎么装物品使得装入…背包问题
常见的背包问题类型大厂面试重点掌握01背包和完全背包即可题目描述有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品能用*次求解怎么装物品使得装入背包里物品价值总和最大。
01背包二维数组解法和滚动数组解法
https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html 视频讲解https://www.bilibili.com/video/BV1cg411g7Y6
题目描述有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。二维数组解法 动规五部曲 二维dp数组dp[i][j] 其中i代表有前 i 个物品可选j代表背包的容量dp值代表对应的最大价值 递推公式 当前 i 和 j 对应的最大价值为 装第i个物品 和 不装第i个物品 两种情况里的较大值其中装第i个物品对应的dp值为dp[i - 1][j - weight[i]] value[i]weight[i]表示第i个物品的重量value[i]代表第i个物品的价值不装第i个物品对应的dp值为dp[i - 1][j]即dp[i][j] max(dp[i - 1][j - weight[i]], dp[i - 1][j] value[i]) 二维dp数组的初始化 当把二维dp数组画图表示出来后可以发现dp[i][j]的值仅由其上方或左上方的元素值决定因此需要把dp数组的第一行和第一列进行初始化第一行的初始化第一行对应只有物品1和背包容量递增的情况由于是01背包所以在背包容量 物品1重量时初始化为0当背包容量 物品1重量时均初始化为物品1的价值第一列的初始化即物品由少到多但背包容量为0的情况全部初始化为0 遍历顺序 内外层for循环是先遍历物品还是背包容量都可以因为二维数组图里无论哪种遍历方式都满足当前元素的上方和左上方元素已有值每层for循环从小到大遍历 无需打印 代码书写问题 问题1如果直接把背包容量n作为dp数组一维的大小则需要在初始化dp数组的第一列时此时第一列为背包容量为1的情况就要使用递推公式因此将dp的一维初始化为n1的大小这样背包容量从0开始初始化不需要递推公式问题2最后直接打印或返回dp数组的最后一个元素即可因为dp数组第[i][j]个元素的含义就是有i个物品可选且背包容量为j的时候最大价值是多少问题3写递推公式的时候由于当前背包的容量可能小于当前物品的重量因此应添加额外判断当小于时只剩下不取当前物品的情况了问题4在初始化dp数组第一行的时候可以直接从weight[0]开始因为前面的位置已经在创建时赋0了不需要进行修改
# 二维数组解法
# m种物品背包容量为n每个物品的重量和价值分别保存在weight和value里
dp [[0] * (n 1) for _ in range(m)]
for j in range(weight[0], n 1):dp[0][j] value[0]
for i in range(1, m):for j in range(1, n 1):if (j - weight[i]) 0:dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i])else:dp[i][j] dp[i - 1][j]
print(dp[-1][-1])滚动数组一维数组解法 在二维数组解法的基础上我们可以发现每次更新dp数组元素时都是依赖且仅依赖于第 i - 1行元素的值因此如果我们仅使用一维数组而在循环过程中滚动更新该数组应该可以实现和二维数组相同的效果为什么要这样做使用一维数组代替二维数组可以显著地优化代码的时间复杂度和空间复杂度如果一下子觉得一维数组写法比较抽象可以先写二维数组之后微调就是一维数组解法动规五部曲 一维dp数组dp[j] 其中j代表背包的容量dp值代表对应的最大价值 递推公式 当前 j 对应的最大价值为 装第i个物品 和 不装第i个物品 两种情况里的较大值其中装第i个物品对应的dp值为dp[j - weight[i]] value[i]weight[i]表示第i个物品的重量value[i]代表第i个物品的价值不装第i个物品对应的dp值为dp[j]即dp[j] max(dp[j], dp[j - weight[i]] value[i]) 一维dp数组的初始化 对应只有第一个物品和背包容量递增的情况由于是01背包所以在背包容量 物品1重量时初始化为0当背包容量 物品1重量时均初始化为物品1的价值 遍历顺序 内外层for循环是先遍历物品、再遍历背包容量因为相当于把二维数组压扁了此时后遍历物品没有意义将得到一个全部为最高价值物品价值的一维数组外层for循环从第一个物品开始遍历顺序遍历内层for循环背包容量从大到小遍历逆序遍历因为要保证每个元素所依赖的前置位元素为二维数组里的左上元素而不是同一行的左边元素 无需打印 代码书写问题 内层for循环逆序遍历时要注意其实索引是n而不是n1
# 一维数组解法
# m种物品背包容量为n每个物品的重量和价值分别保存在weight和value里
dp [0] * (n 1)
for j in range(weight[0], n 1):dp[j] value[0]
for i in range(1, m):for j in range(n, 0, -1):if (j - weight[i]) 0:dp[j] max(dp[j], dp[j - weight[i]] value[i])
print(dp[-1])*416. 分割等和子集
https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html 视频讲解https://www.bilibili.com/video/BV1rt4y1N7jE
考点 动态规划01背包 我的思路 本题可以用回溯暴力求解但大概率超时 视频讲解关键点总结 关键点1分割等和子集等价转化为从集合里取元素使其和值填满集合和值的一半则剩下元素和当前取的元素构成了等和子集关键点2由于每个元素只能取一次并且相当于从前 i 个物品里取物品来填满容量为集合值一半的背包所以本题可以抽象为01背包问题动规五部曲 一维数组dp[j]的含义是当背包容量为 j 时取前 i 个元素i通过外层循环来取替代原有的二维数组能得到的不超过背包容量的最大和值可以等于递推公式 dp[j] max(dp[j], dp[j - nums[i]] nums[i])取当前元素和不取当前元素的较大者 初始化dp初始化为0即可因为背包容量为0时最大值就为0遍历顺序 外层循环遍历元素 i 内存循环遍历容量 j外层循环正向遍历内层循环反向遍历避免将同一元素计算两次 无需打印 我的思路的问题 无思路 代码书写问题 注意内层循环的停止位置 可执行代码
class Solution:def canPartition(self, nums: List[int]) - bool:summation sum(nums)if summation % 2 1:return Falsesummation / 2summation int(summation)dp [0] * (summation 1)for i in range(len(nums)):for j in range(summation, nums[i] - 1, -1):dp[j] max(dp[j], dp[j - nums[i]] nums[i])if dp[-1] int(summation):return Truereturn False
