【C++算法】动态规划背包问题 -＞ 01背包
01背包的核心是：每个背包只可以用一次
P1048 [NOIP 2005 普及组] 采药 - 洛谷
思路讲解：二维朴素dp
f[i][j]是状态表示
i表示我们要遍历的数组，j表示我们遍历的重量
首先我们看题，我们可以得出：
1、所有的用品，只能选一次
2、求最大值
那么我们怎么使用动态规划呢？
- 当这个物品的容量超出这个体积的时候，我们是不是不能选
- 当这个物品小于这个体积的时候，这个物品我们是不是可以考虑
总结：这就涉及到我们的选和不选的问题了
怎么去不选？
当我们遍历i的时候，我们是不是可以不选当前这个物品，我们的状态表示方程
// 不选当前物品 f[i][j]=f[i-1][j]
怎么去选？
当我们遍历 i 的时候，而我们的 j 在遍历重量，是不是只有当我们 j >= 物品的重量才可以去选
注意：我们选完它的物品，此时我们是不是要减去它的重量，在加上它的价值
// 选当前的物品 f[i][j] = max(f[i][j], f[i - 1][j - w[i]]) + v[i];
讲完了，开造！
#include <iostream> using namespace std; const int N = 1005; int x, y; int f[N][N]; int w[N], v[N]; int main() { //输入 cin >> x >> y; for (int i = 1;i <= y;i++)cin >> w[i] >> v[i]; for (int i = 1;i <= y;i++) { for (int j = 0;j <= x;j++) { //不选 f[i][j] = f[i-1][j]; //选 if (j >= w[i]) { f[i][j] = max(f[i][j], f[i - 1][j - w[i]]) + v[i]; } } } cout << f[y][x]; return 0; }优化dp（滚动数组）
大白话讲解：
场景：你在抄作业
- 二位数组：你有两张纸，一张是昨天的答案（第i-1行），一张是今天的答案（第i行）。你可以随时参考昨天的答案，不会搞混
- 一位数组：你只有一张纸，既要保存昨天的答案，又要写今天的答案，还得保证写的时候不能把昨天的答案擦掉
我们先看一下二位数组是怎么存的
场景：你有一张表格
容量0 容量1 容量2 容量3 容量4 物品0 0 0 0 0 0 ← 初始行（没物品） 物品1 0 0 100 100 100 ← 处理完第1个物品 物品2 0 0 100 100 200 ← 处理完第2个物品 物品3 0 0 100 150 200 ← 处理完第3个物品我们可以发现：
- 算第3行（物品3）的时候，只用到了第2行数据
- 算完第3行后，第一行、第二行就没用了
- 每次只需要上一行的数据
那么怎么用一位数组去节省空间呢？
既然只需要上一行，那我干脆只保留一行，不断覆盖更新
一开始： [0, 0, 0, 0, 0] ← 只有一行 处理物品1： [0, 0, 100, 100, 100] ← 覆盖掉原来的 处理物品2： [0, 0, 100, 100, 200] ← 继续覆盖 处理物品3： [0, 0, 100, 150, 200] ← 继续覆盖那么省了多少空间？
- 二维：物品数 X 容量 个格子
- 一位：容量个格子
- eg：如果1000个物品，容量1000，二位要100万格子，一维只要1000个
注意：覆盖原来空间也就是数组，就叫做滚动数组
那为什么从大到小呢？
因为在同一个空间改数据，如果不小心，会把没用的旧数据提前覆盖掉！
eg：容量4
1个物品重量2 价值100
数组：[0, 0, 0, 0, 0] 从小到大（从左往右改）： j=2: 改成 100 → [0, 0, 100, 0, 0] j=3: 用到 j=1，还是 0 → [0, 0, 100, 100, 0] j=4: 用到 j=2，但 j=2 已经被改成 100 了！ 结果：100 + 100 = 200 ❌ 同一个物品用了两次！ 从大到小（从右往左改）： j=4: 用到 j=2，还是 0 → [0, 0, 0, 0, 100] j=3: 用到 j=1，还是 0 → [0, 0, 0, 100, 100] j=2: 用到 j=0，还是 0 → [0, 0, 100, 100, 100] 结果正确！每个物品只用一次 ✅总结：
- 一位数组=只有一行，反复覆盖更新
- 从大到小=从右往左改，避免用刚改过的数据，并且保证每个物品只用一次
#include <iostream> using namespace std; const int N = 10005; int x, y; //int f[N][N]; int f[N]; int w[N], v[N]; int main() { //输入 cin >> x >> y; for (int i = 1;i <= y;i++)cin >> w[i] >> v[i]; for (int i = 1;i <= y;i++) { //for (int j = 0;j <= x;j++) //{ // //不选 // f[i][j] = f[i-1][j]; // //选 // if (j >= w[i]) // { // f[i][j] = max(f[i][j], f[i - 1][j - w[i]]) + v[i]; // } //} for (int j = x;j >= w[i];j--)// 从大到小遍历 { f[j] = max(f[j], f[j - w[i]] + v[i]); } } //cout << f[y][x]; cout << f[x]; return 0; }