06 | 0-1背包：动态规划的Hello World
卢誉声
你好，我是卢誉声。从今天开始，我们正式进入动态规划套路模块。
不知道你是否跟我有过相似的经历，那就是提起动态规划，最先想到的就是背包问题。事实上，背包问题分很多种，大多数人首先遇到的一般是背包中的 0-1 背包问题。
因此，我把这个问题称作 Hello World，这跟我们学习一门新的编程语言十分相似。它很经典，又极具代表性，能很好地展示动态规划思想，对于你掌握动态规划面试题来说，也十分有帮助。
在“初识动态规划”模块中，相信你已经对动态规划问题有了一个比较全面的认识和了解。今天，就让我们用一用前面所学的解题思路，其实就是把总结出来的套路，套用在 0-1 背包问题上，看看能不能解决这道题。
那在开始前呢，我还是先提出一个简单的问题，那就是：为什么将它称作 0-1 背包问题，0-1 代表什么？你不妨带着这个小问题，来学习今天的内容。
0-1 背包问题
我们先来看看 0-1 背包问题的描述。
问题：给你一个可放总重量为 的背包和 个物品，对每个物品，有重量 和价值 两个属性，那么第 个物品的重量为 ，价值为 。现在让你用这个背包装物品，问最多能装的价值是多少？
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入浅出地介绍了动态规划中的经典案例——0-1背包问题。作者首先引出了0-1背包问题的背景和重要性，将其比喻为动态规划的“Hello World”，并解释了为什么称之为0-1背包问题。文章详细分析了该问题的算法问题，引导读者从贪心算法和穷举的角度思考，最终确定使用动态规划解决问题。作者还列举了动态规划问题的特征，包括重叠子问题、无后效性和最优子结构，以及如何写出状态转移方程。最后，作者给出了递归形式的状态转移过程描述和状态转移方程，为读者提供了完整的解题思路。文章还提供了Java和C++的代码实现，帮助读者更好地理解动态规划的具体应用。整篇文章通俗易懂，逻辑清晰，对于初学者来说是一篇很好的学习资料。文章还对0-1背包问题进行了延伸，介绍了一个相关的动态规划问题，帮助读者更好地理解动态规划问题的应用和变种。文章内容丰富，涵盖了动态规划的基本概念和具体应用，对于想深入了解动态规划算法的读者来说是一篇不可多得的好文。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《动态规划面试宝典》，新⼈⾸单¥59
《动态规划面试宝典》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(33)
- 最新
- 精选
浅语清风课程难度越来越大了，对于对于初学者来说看一遍是根本不够的，要反复学习，不断积累，编程实践。我一定要攻克动态规划的难关！作者回复: 我们一起加油！有任何相关问题，都欢迎留言讨论。我也会尽我所能帮你解答。
2020-09-2510
BBQ感谢老师的细心讲解，怎么感觉越写越简单了呢。 😀 把空间复杂度优化了一下，用一个一维数组，倒着走，就不会产生重复计算了。 def lastStoneWeightII(self, stones: List[int]) -> int: total = sum(stones) size = (total)//2+1 #这个要注意，如果容量要达到size，大小要是size + 1 dp = [0] * size for i in range(len(stones)): j = size - 1 while j >= stones[i]: dp[j] = max(dp[j], dp[j-stones[i]] + stones[i]) j-= 1 return total - dp[-1] - dp[-1]作者回复: 恩，这样处理没有问题。顶上去，让大家看到。
2021-03-104
冬风向左吹没太理解这里：dp[tn-1][rw-w[tn]] + v[tn]。放入物品前的价值+放入特别的价值。为什么放入特别前的价值 rw-w[tn]，这里要减w[tn]呢。放入物品前的价值不就是dp[tn-1][rw]吗？作者回复: 并不是这样，因为 dp[tn][rw]是背包在处理第tn个物品后背包剩余rw容量的最优解，那么如果我们没有把第tn件物品放进去，那么肯定就是dp[tn-1][rw]。当时如果我们要把第tn件物品放进去，那么放进去背包之后容量就只剩下了rw-w[tn]，所以需要取得就是dp[tn-1][rw-w[tn]]（也就是在容量只剩下rw-w[tn]得情况下，处理第tn-1个物品时最优是多少）。
2020-11-0742
Roy Liang#include <iostream> #include <vector> #include <cmath> #include <cstring> using namespace std; int DP(const std::vector<int>& w, const std::vector<int>& v, int N, int W) { int dp[N+1][W+1]; memset(dp, 0, sizeof(dp)); // 创建备忘录 for (int tn = 1; tn < N + 1; tn++) { // 遍历每一件物品 for (int rw = 1; rw < W + 1; rw++) { // 背包容量有多大就还要计算多少次 if (rw < w[tn]) { // 当背包容量小于第tn件物品重量时，只能放入前tn-1件 dp[tn][rw] = dp[tn-1][rw]; } else { // 当背包容量还大于第tn件物品重量时，进一步作出决策 dp[tn][rw] = max(dp[tn-1][rw], dp[tn-1][rw-w[tn]] + v[tn]); } } } return dp[N][W]; } int main() { int N, i, sum = 0, t, part1, part2; vector<int> w, v; w.push_back(0); v.push_back(0); cin >> N; for (i = 1; i <= N; i++) { cin >> t; sum += t; w.push_back(t); v.push_back(t); } part1 = DP(w, v, N, sum / 2); part2 = sum - part1; cout << abs(part1 - part2) << endl; }作者回复: 赞，没问题。顶上去！
2020-10-192
coder关于粉碎石头（力扣上的题：1049. 最后一块石头的重量 II）的问题的思考： 1. 可以把石头分为两堆，这两堆的重量尽量均衡，才能产生最小的差值 2. 那么就相当于把所有石头的总重量除以2，作为背包的容量，然后看最大能装入多少重量的石头 3. 从而转化成背包问题作者回复: 这样是可以的。赞，让大家看到。
2021-12-2121
樟树林老师，关于背包问题哈，背包容量为2，物品个数为3的背包，按照你上述计算得出的结果是3，但实际结果应为6。这个问题，老师能解释一下吗？作者回复: 这个背包内可以容纳的物品只取决于背包的容量和物品的重量，示例数据里背包容量为2的情况下，最优解肯定是3，因为永远只能装下一个物品，这个是不是对问题的理解有什么偏差。
2021-01-2041
Smile石头碾碎问题 public int lastStoneWeightII(int[] stones) { int sum = 0; for (int i = 0; i <stones.length; i++) { sum+=stones[i]; } int N = stones.length; // 个数 int W = sum/2; //总重量 int[] w = stones; //重量 int[] v = stones; //价值 int[][] dp = new int[N+1][W+1]; //初始化状态 for (int i = 0; i < N+1; i++) { dp[i][0]=0; } for (int i = 0; i < W+1; i++) { dp[0][i]=0; } for (int tn = 1; tn < N+1; tn++) { for (int rw = 1; rw < W + 1; rw++) { if(rw<w[tn-1]){ dp[tn][rw] = dp[tn-1][rw]; }else{ dp[tn][rw] = Math.max(dp[tn-1][rw],dp[tn-1][rw-w[tn-1]]+v[tn-1]); } } } return Math.abs(sum-2*dp[N][W]); }作者回复: 这个代码没问题，下标正确！
2023-11-16归属地：浙江- Smiledp[tn][rw] = Math.max(dp[tn-1][rw], dp[tn-1][rw-w[tn]] + v[tn]); 这个是有问题的，w[tn]实际上是 tn+1的物品了，这个地方都是 tn-1，思路应该是对的，但是这个代码翻译是有问题的，发现评论区好多有问题
作者回复: 应无问题，代码中的w和v第0个位置放的是0，所以w[1]就是第一个物体，所以这里是w[tn]和v[tn]，而不是w[tn-1]和v[tn-1]。
2023-11-16归属地：浙江 - Smilepublic int max(int[] w,int[] v,int W,int N){ //第几个物体的时候的最大价值 // dp[tn][rw] 表示浏览过 tn 件商品，能装下 rw 重量的最大剩余价值 // 题目的结果就是 dp[N][W] // rw < w[tn] dp[tn][rw] = dp[tn-1][rw] // 否则 dp[tn][rw] = max(dp[tn-1][rw],dp[tn-1][rw-w[tn]+v[tn]]) //初始状态 // dp[tn][0] = 0 dp[0][rw] = 0; int[][] dp = new int[N][W]; for (int i = 0; i < N; i++) { dp[i][0]=0; } for (int i = 0; i < W; i++) { dp[0][i]=0; } for (int tn = 1; tn <= N; tn++) { for (int rw =1 ; rw <= W; rw++) { if(rw<w[tn]){ dp[tn][rw] = dp[tn-1][rw]; }else{ dp[tn][rw] = Math.max(dp[tn-1][rw],dp[tn-1][rw-w[tn]]+v[tn]); } } } return dp[N][W]; }
作者回复: 代码中可能有问题，你再检查一下。定义的dp下标范围是0..N-1和0..W-1 但是for循环中实际遍历的时候可能会访问dp的下标是0..N和0..W，这样会越界。
2023-11-16归属地：浙江 
风清扬参考评论里 Roy Liang的代码，修改了下代码，添加了部分注释： #include <iostream> #include <vector> #include <cmath> #include <cstring> #include <numeric> // std::accumulate using namespace std; int DP(const std::vector<int>& w, const std::vector<int>& v, int N, int W) { //DP[i][j]，当可以选择前i(含)个物品时，背包容量为j时最大的价值 int dp[N+1][W+1]; memset(dp, 0, sizeof(dp)); // 创建备忘录 for (int tn = 1; tn < N + 1; tn++) { // 遍历每一件物品 for (int rw = 1; rw < W + 1; rw++) { // 背包容量有多大就还要计算多少次 if (rw < w[tn]) { // 当背包容量小于第tn件物品重量时，只能放入前tn-1件 dp[tn][rw] = dp[tn-1][rw]; } else { // 当背包容量还大于第tn件物品重量时，进一步作出决策 dp[tn][rw] = max(dp[tn-1][rw], dp[tn-1][rw-w[tn]] + v[tn]); } } } return dp[N][W]; } int main() { int N = 6; //粉碎石头问题转换为0-1背包，这里价值与重量相同 vector<int> w = {0,1,2,1,7,9,4}; vector<int> v = {0,1,2,1,7,9,4}; //计算当前所有石头的重量和 int sum = std::accumulate(w.begin(),w.end(),0); //转换为0-1背包问题，在背包容量为sum/2的情况下，尽量让价值最大（重量最大）接近sum/2,因此part2-part1绝对值越小 int part1 = DP(w, v, N, sum / 2); int part2 = sum - part1; cout << "part1:"<<part1<<",part2:"<<part2<<",abs:"<<abs(part1 - part2) << endl; return 0; }作者回复: 给你点个赞，注释能帮助到更多人！
2023-03-05归属地：广东2
收起评论
