休闲旅游网站建设wordpress文章部分显示图片
大家好，今天 给大家讲解01背包问题
有N件物品和一个容量为V的背包。第i件物品的体积是c[i]，价值是w[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
01背包问题是典型的动态规划问题，我们拿葡萄矿泉水和西瓜举例子
这道题确实可以用暴力来做，但凡这给的数是10的七次方你咋办？
今天就教你们可以轻松拿捏这道题的方法：DP（动态规划）
要想要解出来这道题，咱们得先列一个表格
然后咱们的每个表格都要填写该表格所在列的背包容量最多可以在所在行的物品及以上所获得的价值总和最多能有多少
你是不是听蒙圈了？
那你就蒙圈吧 没有关系，下面我给你放一张图你就明白了
看懂了吧，这回还没看懂我真没办法了私信我吧
首先来看第零行
肯定都是零嘛，第零行是空气价值为0，无论如何肯定总价值是0
接下来看第零列，很明显，由于背包大小为0，装不了任何东西，所以都填0.
我们最终要求的答案在第六列第三航。
接着问题来了，第一列第一行的单元格怎么填？
很简单，葡萄的重量是2，背包大小只有1，连葡萄的大小都不够，所以填0
接下来看第一行，葡萄的重量是2，从第二列开始所有背包的重量都≥2，葡萄的价值为3，所以第一行的第2-6列均为3.
接下来看第二行，很明显，第二行的第1、2个背包的重量不够矿泉水的重量（3），所以它们的最优解全部继承于上方的单元格
接下来填写第二行第三列的单元格，该列的背包容量为3，葡萄和矿泉水都可以被其装进去，那么我们该比较了：
装完葡萄之后就不可以再装其他物品了，装葡萄的最优解为葡萄的价值，3.
装矿泉水之后，也不能装其他东西了，所以装矿泉水的最优解为矿泉水的价值，5.
5>3，所以这里应该填写5.
二行四列可以只装葡萄或只装矿泉水或只装西瓜（西瓜在第三行才会考虑，所以这里不考虑西瓜的情况）（因为这是01背包问题，01的意思是一个物品装的数量只有0和1，所以装两个葡萄是不可能的）所以也填5.
接着看二行的第五列，这一列背包容量达到了5，可以同时容纳葡萄和矿泉水， 所以这一格填8.
第六格同样填8.
接下来看第三行，这一行会考虑西瓜，第1-3列由于不够装西瓜，所以直接继承第二行的结果
第四列装完西瓜后没地方放别的东西了，所以价值是6，6>5，所以填6
第五列装完西瓜同样不能放别的东西，6<8，所以填写8.
最后，三行六列便是我们最终的答案。
这一格放西瓜后还有6-4=2的位置，正好放一个葡萄。这种方案的总价值是6+3=9，9比8大。
所以这一格填写9。
最后的答案便是9了。
而我们刚刚的表格再编程中可以用一个二维数组dp来表示。
总结一下思路：
-
状态定义：设
dp[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值。 -
状态转移方程：
- 不选第
i件物品：dp[i][j] = dp[i-1][j] - 选择第
i件物品（前提是j >= w[i]）：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
- 不选第
-
初始化：
dp[...]=0，即没有物品时，价值都为0。
-
目标：
dp[n][W]，也就是表格的最后一行最后一列
然后上模板代码
#include <iostream>
#include <vector>
using namespace std;int main() {int n, W; // n是物品个数，W是背包容量cin >> n >> W;vector<int> w(n + 1), v(n + 1); // w是重量数组，v是价值数组for (int i = 1; i <= n; i++) {cin >> w[i] >> v[i];}vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));// 动态规划填表for (int i = 1; i <= n; i++) {for (int j = 0; j <= W; j++) {if (j >= w[i]) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);} else {dp[i][j] = dp[i - 1][j];}}}cout << dp[n][W] << endl; // 输出最大价值return 0;
}
但是这个代码有一个地方还可以优化，空间上，可以只用一维数组dp[j]来存储上一行的结果，这样可以将空间复杂度从O(nW)降低到O(W)。
vector<int> dp(W + 1, 0);
for (int i = 1; i <= n; i++) {for (int j = W; j >= w[i]; j--) {dp[j] = max(dp[j], dp[j - w[i]] + v[i]);}
}
cout << dp[W] << endl;
注意一下，第二种写法中一维数组的实现中，内层循环需要倒序进行，以确保每次计算使用的是上一轮的结果。
好了，这一篇博客就写到这里，求点赞收藏关注 ，你们的支持就是我更新的最大动力！