01 背包
有N件物品和⼀个最多能被重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装⼊背包里物品价值总和最大？
1. 例题（二维数组解法）
题目
背包最大重量为4
| 重量 | 价值 | |
| 物品0 | 1 | 15 |
| 物品1 | 3 |
20 |
| 物品2 | 4 |
30 |
问：背包能背的物品最大价值是多少？
思路
五部曲
1.数组含义
使用二维数组 dp[i][j]，含义：从下标为 [ 0 ∼ i ] 的物品中任意取，放入容量为 j jj 的背包，价值总和最大为多少
2.递推公式由两个方向推出
一、不放物品 i 的最大价值
背包容量为 j，但不放物品 i 时的最大价值，即 dp[i-1][j]
二、放物品 i 的最大价值
先找到 dp[i-1][j-weight[i]]，含义：i − 1 保证了不放物品 i，背包容量为 j − w e i g h t [ i ] 其实就是为了给后续放物品 i 一个预留量，保证放了物品 i ii 后背包不会溢出，所以最大价值为 dp[i-1][j-weight[i]]+value[i]
递推公式：
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w e i g h t [ i ] ] + v a l u e [ i ] )
3.数组初始化
背包容量 j jj 为零时，显然价值为零
只选物品0，即第一行，显然只要物品0重量小于等于背包重量 j jj，价值就为物品0的价值，否则为零
4.确定遍历顺序
先遍历背包还是物品都可以
dp[i][j] 所需的数据在其左上方
5.测试用例
代码展示
#include <iostream> #include <cmath> #include <vector> using namespace std; void test_2_wei_bag_problem1() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1)); for (int i = 1; i < bagWeight + 1; i++) { if (weight[0] <= i) { dp[0][i] = value[0]; } } for (int j = 1; j < bagWeight + 1; j++) { for (int i = 1; i < weight.size(); i++) { if (j < weight[i]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); } } } cout << dp[weight.size() - 1][bagWeight]; } int main() { test_2_wei_bag_problem1(); return 0; }
2. 例题（滚动数组解法）
还是之前的例子，可以用滚动数组将数组降为一维
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w e i g h t [ i ] ] + v a l u e [ i ] )
由递推公式得： dp[i][j] 只和它的上一行有关，且有关元素的行数为 i − 1 i-1i−1，列数 ≤ j \le j≤j。那么我们就可以将数组压缩成一维
dp[i−1][j−weight[i]] |
dp[i−1][j] |
| 欲求元素 |
看这张表，如果数组是一维的情况，那么在算出欲求元素后，其实是将欲求元素覆盖掉 dp[i-1][j]，并且我们的遍历顺序也要改变。在二维情况下，我们是按从左到右的顺序求的，但在一维中，必须从右向左！因为在求欲求元素时，我们要保证 dp[i-1][j-weight[i]] 未被覆盖！同时，必须按照先遍历物品，再嵌套遍历背包的顺序。
#include <iostream> #include <cmath> #include <vector> using namespace std; void test_1_wei_bag_problem1() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; vector<int> dp(bagWeight + 1); for (int i = 0; i < weight.size(); i++) { for (int j = bagWeight; j >= weight[i]; j--) { dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } cout << dp[bagWeight]; } int main() { test_1_wei_bag_problem1(); return 0; }
