本文最后更新于 44 天前，其中的信息可能已经有所发展或是发生改变。
视频讲解
例题
题目要求：
假设你是一个高中生，准备去参加一个为期两天的户外活动。你有一个背包，它的最大承重是10公斤。现在你有以下几样物品，每样物品都有一定的重量和价值，你希望从这些物品中选择一些，使得背包里的物品总重量不超过10公斤，同时让物品的总价值尽可能高。
物品列表如下：
- 水壶（重量2公斤，价值50元）
- 食物（重量3公斤，价值100元）
- 毛巾（重量1公斤，价值10元）
- 相机（重量4公斤，价值300元）
- 便携式帐篷（重量5公斤，价值200元）
背包问题就是要解决：如何选择这些物品，使得背包里的物品总价值最高，同时不超过10公斤的承重限制。
个人思路
思路：
根据动态规划表格可知，每一个格子即为当前背包容量的最优解，那么下一格子则可以利用先前所得的最优价进行比较（前提是能装得下，装不下则继承先前相同容量最优解）装与不装用max函数判断。
代码演示
#include <iostream>
#include <vector>
using namespace std;
// 物品的结构体，包含重量和价值
struct Item {
int weight;
int value;
};
// 背包问题的解决方案
int knapSack(int W, vector<Item>& items, int n) {
// 创建一个二维数组，用于保存中间结果
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
// 通过动态规划填充dp数组
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
// 如果当前物品的重量小于等于背包的当前容量
if (items[i - 1].weight <= w) {
// 选择“放入背包”和“不放入背包”中价值较大的一个
dp[i][w] = max(items[i - 1].value + dp[i - 1][w - items[i - 1].weight], dp[i - 1][w]);
} else {
// 当前物品重量大于背包容量，不能放入背包
dp[i][w] = dp[i - 1][w];
}
}
}
// 返回dp数组的最后一个元素，即最大价值
return dp[n][W];
}
int main() {
// 物品列表
vector<Item> items = {{2, 50}, {3, 100}, {1, 10}, {4, 300}, {5, 200}};
// 背包的最大承重
int W = 10;
// 物品的数量
int n = items.size();
// 调用knapSack函数计算最大价值
int max_value = knapSack(W, items, n);
cout << "The maximum value that can be put in a knapsack of capacity " << W << " is " << max_value << endl;
return 0;
}
细节注释
- 为何采用vector容器函数：无需手动管理内存（数组大小）且有丰富的接口（push_back…等等）【虽然这里没展现出他的优势】
- 如何用vector创建一个二维数组：首先用vector创建一个一维数组，vector<int> dp（n，0）【创建一个含有n个元素全是0的一维数组】，以此类推创建一个二维数组是vector<vector<int>> dp（n，vector<int>（m，0））【创建一个n元素是一个一维数组（有m个元素全是0的数组）的一维数组即为二维数组】
优化（空间复杂度）
滚动规划：
当我们进行背包问题运算时，需要创建一串表格如果面积过大就会造成内存的浪费（毕竟我们需要的只是最终结果而不是内容的记录），此时就需要滚动规划（即为一维化）
原理：
根据上方二维数组原理可知，确定方格中的最优解只与本行与上一行相关（上方与列表前方的数值对比）且为了不干扰前方数组，我们采取倒序分析方法。
操作步骤：
1.用一个一维数组存储物品的价值和重量
2.再用一个一维数组用来当作操作台（前提要填充0以便后续操作）
代码演示
#include <iostream>
#include <vector>
using namespace std;
// 物品的结构体，包含重量和价值
struct Item {
int weight;
int value;
};
// 背包问题的解决方案，使用滚动规划优化空间复杂度
int knapSack(int W, vector<Item>& items) {
int n = items.size();
// 只需要保存一维数组即可，大小为背包容量加一
vector<int> dp(W + 1, 0);
// 通过动态规划填充dp数组
for (int i = 0; i < n; i++) {
// 注意这里必须从后向前更新，以避免覆盖还未使用的数据
for (int w = W; w >= items[i].weight; w--) {
// 选择“放入背包”和“不放入背包”中价值较大的一个
dp[w] = max(dp[w], items[i].value + dp[w - items[i].weight]);
}
}
// 返回最大价值
return dp[W];
}
int main() {
// 物品列表
vector<Item> items = {{2, 50}, {3, 100}, {1, 10}, {4, 300}, {5, 200}};
// 背包的最大承重
int W = 10;
// 调用knapSack函数计算最大价值
int max_value = knapSack(W, items);
cout << "The maximum value that can be put in a knapsack of capacity " << W << " is " << max_value << endl;
return 0;
}
细节注释
- 动态规划中出现两个循环，其中最外层for目的是用于后续item[i]中检索物品，所以他不用讲究顺序（上限为物品总量）最内层for目的是倒着检索物品（一般来说如果物品重量很大也是一点一点来检索的，比如1000个，此处会耽误运算速率，后续会学到二进制优化）
- 为什么动态规划中第二个for中并没有和之前的代码一样没有if-else筛选呢？原因是滚动和列表有很大不同，列表中各个值不能覆盖，所以w也代表的表中的横/纵坐标，有记录的作用（而滚动中的for并没有记录作用，因为是倒过来的，那么一维数组的最左侧值就是物品列表中重量最小的物品的价值）我们只有数组中最后一位数，所以在for循环中的条件就可以直接用来筛选。