背包问题入门
1.什么是背包
背包问题是动态规划部分的经典题型。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。 一般来讲，背包问题有以下几种分类：
1. 01背包问题
2. 完全背包问题
3. 多重背包问题
在leetcode刷题过程中，我们需要掌握这几种背包问题的写法。要注意的是，有些题目并不会直接告诉你这是一道背包问题，而是需要我们利用发散思维将问题转换为背包问题，以此来找到解题方法。
01背包问题
1.题目
最基本的背包问题就是01背包问题（01 knapsack problem）：一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
我们的目标是书包内物品的总价值，而变量是物品和书包的限重，所以我们可定义状态dp，首先使用二维数组来表示dp过程：
dp[i][j]表示将前i件物品装进最大容量为j的背包所获得的最大价值，0 <= i <= N, 0 <= j <= W
此时根据dp表示的含义，自然而然dp[0][j]为0，因为此时并未装进物品。此时当i > 0时，有两种情况：
- 不装第
i件物品，即dp[i][j] = dp[i - 1][j] - 装入第
i件物品（前提是剩余容量能装下），即dp[i][j] = dp[i - 1][j - w[i]] + v[i]
那么由此得到状态转移方程：
dp[i][j] = max(dp[i − 1][j], dp[i − 1][j − w[i]] + v[i]) // j >= w[i]
完整代码如下：
for(int i = 1; i < w.size(); i++) { // 遍历物品
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
if (j < w[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
此时先遍历的是物品，再遍历背包容量，反之也是可以的，这里注意到j的遍历是正向的，因为下一层使用的是上一层的状态，具体而言，需要的是左上角的信息。
上述状态转移方程可知，dp[i][j]的值只与dp[i - 1][j]有关，所以我们使用动态规划常用的方法（滚动数组）来对空间复杂度进行优化，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。此时dp[j]表示容量为j的背包，所装的物品最大价值。同理可得到状态转移方程：
dp[j] = max(dp[j], dp[j - w[i]] + v[i])
初始化时，将dp[i]全部初始化为0.完整代码如下：
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]);
}
}
这里我们发现，j的遍历顺序是逆序的。原因是：如果是正向计算，那么会出现状态重合的情况，例如下面的例子：背包容量为4，物品属性如下：
| 物品重量 | 物品价值 |
|---|---|
| 1 | 15 |
| 3 | 20 |
| 4 | 30 |
此时dp[1] = 15, dp[2] = dp[2 - w[0]] + v[0] = d[1] + 15 = 30。可以注意到这里dp[2]恰巧用到了dp[1]的数据，也就是说此时第一个物品被装了两次。那么为了避免这种情况，我们就需要对j进行逆序遍历，这样用到前面的数据时，前面的数据还没有被遍历到，其状态是0，模拟的就是一件物品只能被装进去一次。同时，i和j的遍历顺序也不能交换，如果j放在外层，那么遍历的结果是背包只放了一件物品。
完整的代码如下：
void test_1_wei_bag_problem() {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
// 初始化
vector<int> dp(bagWeight + 1, 0);
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] << endl;
}
int main() {
test_1_wei_bag_problem();
}
学习完以上的知识，就可以试着做一做leetcode的416和1049题，这两道题是经典的可以转化为背包问题的题目。下一篇博客将总结多重背包问题。