力扣题目：01背包问题（二维数组）
刷题时长：参考题解
解题方法：动态规划 + 二维dp数组
复杂度分析
- 时间
- 空间
问题总结文章来源：https://www.toymoban.com/news/detail-643108.html
- 理解递推公式困难
本题收获文章来源地址https://www.toymoban.com/news/detail-643108.html
- 动规思路：两层for循环，第一层i遍历物品，第二层j枚举背包容量以内所有值
- 确定dp数组及下标的含义：dp[i][j] 表示从下标为[0-i]的物品范围 中任意取，放进容量为j的背包后价值总和的最大值
- 确定递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
- 当背包容量小于物品重量，不放物品，此时价值总和为dp[i - 1][j]。即当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。
- 当背包容量大于等于物品重量，放入物品i，此时价值总和最大值为dp[i - 1][j - weight[i]]。即为了放入物品i，先找到背包容量刚好完全放不下物品i时的价值总和最高值，再加上物品i的价值，此时即为背包容量足够时选择放入物品i后的总价值。
- dp数组的初始化：
-
# 二维数组 dp = [[0] * (bagweight + 1) for _ in range(len(weight))] # 初始化 for j in range(weight[0], bagweight + 1): dp[0][j] = value[0] - 确定遍历顺序：二维数组中，先遍历背包容量还是物品都可行
力扣题目：01背包问题（滚动数组）
刷题时长：参考题解
解题方法：动态规划 + 一维dp数组
复杂度分析
- 时间
- 空间
问题总结
- for循环遍历顺序为什么不能交换
本题收获
- 动规思路
- 确定dp数组及下标的含义：在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]
- 确定递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
- 此时dp[j]有两个选择，一个是取自己dp[j]，相当于二维dp数组中的dp[i-1][j]，即不放物品i；一个是取dp[j - weight[i]] + value[i]，即放物品i。两者取大的得到价值最大值
- dp数组的初始化：都为0
- 确定遍历顺序：正序遍历物品，倒序遍历背包
- 相比二维数组，用一维数组实现的区别：
- 双循环的次序不能颠倒，必须先物品，再背包：dp[j]代表了二维数组中上一层放入物品i-1后的最大价值，和当前我们放入物品i后的总价值进行对比，比较之后再覆盖并更新为当前最大值
- 背包的遍历顺序必须为倒序：以保证物品i只被放入了一次
力扣题目：#416. 分割等和子集
刷题时长：参考题解后10min
解题方法：动态规划
复杂度分析
- 时间O(n^2)
- 空间O(n)
问题总结
- 如何能抽象为01背包问题
本题收获
- 转换为01背包问题：本题中每一个元素的数值既是重量，也是价值
- 背包的体积为sum / 2
- 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
- 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入
- 动规思路
- 确定dp数组及下标的含义：容量为j的背包，所背的物品价值最大可以为dp[j]
- 确定递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
- dp数组的初始化：都为0
- 确定遍历顺序：第一层正序，第二层倒序
- 在第二层循环中左边界设为i-1，即背包容量枚举到大小等于i时就跳出，因为此时背包是装不下物品i的，无需再进一步写条件判断背包容量是否足够
到了这里，关于力扣算法刷题Day42｜动态规划：01背包问题 分割等和子集的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
