01背包的核心是每个背包只可以用一次P1048 [NOIP 2005 普及组] 采药 - 洛谷思路讲解二维朴素dpf[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容量41个物品重量2 价值100数组[0, 0, 0, 0, 0] 从小到大从左往右改 j2: 改成 100 → [0, 0, 100, 0, 0] j3: 用到 j1还是 0 → [0, 0, 100, 100, 0] j4: 用到 j2但 j2 已经被改成 100 了 结果100 100 200 ❌ 同一个物品用了两次 从大到小从右往左改 j4: 用到 j2还是 0 → [0, 0, 0, 0, 100] j3: 用到 j1还是 0 → [0, 0, 0, 100, 100] j2: 用到 j0还是 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; }