力扣题目：01背包问题（二维数组）
刷题时长：参考题解
解题方法：动态规划 + 二维dp数组
复杂度分析
- 时间
- 空间
问题总结
- 理解递推公式困难
本题收获
- 动规思路：两层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
- 确定遍历顺序：正序遍历物品，倒序遍历背包，以保证物品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的，无需再进一步写条件判断背包容量是否足够
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
什么是多表查询？如何在MySQL中进行多表查询？ 多表查询就是在一个查询中涉及到多个表，通过特定的关联方式连接多个表，并根据条件从中查询出所需要的数据。 多表查询是关系型数据库中最为基础的应用之一。 一个比较典型的例子就是，我们在查询一个订单的详细信息时，需要…
