07｜完全背包：深入理解背包问题
完全背包问题
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文深入探讨了完全背包问题及其解决方法。通过分析算法问题特征，文章确定了动态规划适合解决完全背包问题。在推导状态转移方程时，详细介绍了动态规划解题框架的应用，包括初始化状态、状态参数、决策和备忘录的使用。文章还提供了Java和C++的代码实现，并对时间复杂度进行了优化讨论。最后，通过改进状态转移方程，消除了重复计算，提出了优化后的状态转移方程。文章还介绍了如何优化动态规划的空间复杂度，通过滚动数组的方式将庞大的状态转移表优化成只有两行的数组。通过深入的分析和清晰的逻辑，帮助读者更好地理解了完全背包问题及其解题思路。文章还提出了如何优化动态规划的时间复杂度和空间复杂度的方法，为读者提供了进一步优化算法的思路。
《动态规划面试宝典》，新⼈⾸单¥59
全部留言(25)
- 最新
- 精选
- Z完全背包空间优化，是否用一维数组就行了。 代码： int bag(int[] w, int[] v, int N, int W) { int[] dp = new int[W+1]; // 依次遍历给定物品 for (int tn = 1; tn < N + 1; tn++) { // 当前背包容量 for (int rw = 1; rw < W + 1; rw++) { if (w[tn] <= rw) { dp[rw] = Math.max(dp[rw], dp[rw-w[tn]] + v[tn]); } } } return dp[W]; }
作者回复: 这个空间优化没有问题。
2020-11-0310 
norton/Dark
滚动数组那描述太绕了，排班也不好对比。意思就是tn和tn-1交替使用0和1行吧，这个技巧没用过的人，可能不理解滚动数组是怎么滚的作者回复: 嗯，你的理解是正确的。意思是 tn 和 tn-1 交替使用数组的 0 行和 1 行。 补充一下背景，让跟多人能看到： 滚动数组的方法在朴素算法当中使用的较为广泛，比如说，读取一个超大文本文件的每一行这样的问题，我们就不希望一次性将整个文本文件加载进入内存，这是因为我们需要的可能只是整个文本文件当中的极个别信息：比如行数、包含某个特定字符的行等等。 一般，我们可以考虑使用求余的方法，来实现周而复始的复用有限的数组空间。
2020-09-285- Paul Shan思考题 每个物品有固定数目，这里递归还要加一个变量记录当前元素所剩的物品个数，这是一个三元递归的问题。 也可以转为为0-1背包问题，将每个物品的数目展开，看成是不同的物体，0-1背包的解法并没有限制所有物品都不同。
作者回复: 如果你说的三元递归说的是状态转移参数，递归是状态转移的过程。 那么对于第一个问题这里其实不用再追加一个参数，因为其实多重背包相对于完全背包只是加入了对数量的限制，因此只需要在遍历物品数量计算DP[i][j]的最优解的时候加上数量作为限制即可，不需要在状态转移中再追加新的参数，增加空间复杂度。 对于你的第二个思路，的确可以直接将物品按照数量展开，直接把多重背包转化成0-1背包，这个思路朴素简单而且好用。
2020-09-293 
宋不肥老师讲的很好！但是老师的图实在是画的二义性很多啊比如dp（2,3 -0*3）+0.3*k ...等等的表达，一边设计到容量的变化，一边又是价值，dp在内外表示的意思就是不一样的，虽然看懂了，但这种图看的真的很难受啊作者回复: 恩，在图文以及前后文符号使用的一致性上的确可以做得更好。
2020-10-301- CDMath.max(dp[tn][rw], dp[tn][rw-w[tn]] + v[tn]) 请麻烦 好好解释一下 和之前的 Math.max(dp[tn-1][rw], dp[tn-1][rw-w[tn]] + v[tn]) 从你的画的图中也看不到 有重复计算的
作者回复: 在第7课中，搜索这个关键字定位内容：“不知道你发现了没有，在改进后的代码中没有 k 参与计算了 ......” 这里就是对重复计算的重叠子问题的解释，这个图应该已经比较清晰了，比如求DP(3,5)，需要求解DP(2,5)、DP(2,4)、DP(2,3)、DP(2,2)、DP(2,1)、DP(2,0)，如果要求解DP(3,4)的时候需要求解DP(2,4)、DP(2,3)、DP(2,2)、DP(2,1)、DP(2,0)，这里就有5个重叠子问题。这相当于我们求解DP(3,4)后再求解一个DP(2,5)即可。 图中每个框都包含了右侧问题的所有子问题，这是显而易见的。
2020-10-241 
子夜2104老师讲的太好了，让人看了，还想继续读下一篇。 我觉得0 1背包是跟前n-1个物品比较，完全背包是跟当前物品的前m-1次比较，在代码上的差异主要体现在是用dp[i-1][j]还是dp[i][j]。作者回复: 谢谢你！ 另外，你的对于0-1背包问题的描述，完全正确。
2020-10-111- norton/Dark时间复杂度物品数量不好理解，有物品类型数量n和单个物品取k个,k平方是怎么出现的呢？少了一步骤，可能会让大多数人注意力断供。
作者回复: 这里时间复杂度的确有问题，应该是O(k * v^2)。已更新。
2020-09-281 
李晓清把数量展开，就变成了0-1背包问题，如：w=[3,2,1]，v=[5,3,2] ,数量n=[2,2,3]， 展开之后：w=[3,3,2,2,1,1,1]，v=[5,5,3,3,2,2,2]，然后就可以用0-1背包算法解决。作者回复: 对的
2023-07-20归属地：北京
风清扬int dp[N+1][W+1]; // 创建备忘录 memset(dp, 0, sizeof(dp)); // 初始化状态 for (int i = 0; i < N + 1; i++) { dp[i][0] = 0; } for (int j = 0; j < W + 1; j++) { dp[0][j] = 0; } C++代码这里前面都memset了，这两个循环应该没必要了吧？作者回复: 这里主要是为了显式说明第一行、第一列初始化为0。
2023-03-11归属地：广东- Geek_48cca1O(kv ^2)是指数级别的复杂度么 原文：虽然完全背包问题比 0-1 背包问题更复杂一些，但是，出现指数级别的复杂度可不是一件好事
作者回复: O(KV^2)并不是指数级别的复杂度，这里原文有错误，已修正。
2023-02-08归属地：广东
