背包容量有限，每件宝贝"拿或不拿"——怎么选最值钱？
你要背一个限重 5 斤的背包去春游，柜子里有若干件宝贝，每件有重量和价值。宝贝不能切开：要么整件装进去（1），要么不装（0）——这就是"0/1"的来历。问题：怎么挑，让背包里宝贝的总价值最大？件数少时可以穷举（每件"拿/不拿"两种，共 2ⁿ 种组合），但 n 一大就爆炸——上 DP：对每件宝贝问一句"拿它，还是放下它"，两种情况谁价值大听谁的。
注意区分：0/1 背包 = 每件最多拿一次；完全背包 = 同种宝贝可以拿多份（比如水可以买好几瓶）。本课只考 0/1。
w[i]、价值 v[i]；背包容量 W，每件至多拿一次，求总价值最大。状态 dp[i][j] = 只考虑前 i 件、容量 j 时的最大价值；转移 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])（不拿 / 拿）。左边是"选宝贝"现场（容量 5，三件宝贝，最优选 2+3 号）；右边是 DP 填好的二维表——答案就藏在最后一格 dp[3][5] = 9。
题目：n 件物品，第 i 件重量 w[i]、价值 v[i]；背包容量 W。每件至多拿一次（拿 = 1，不拿 = 0），求背包内总价值最大。穷举：每件两种选择，共 2ⁿ 种组合。n=3 时 8 种，手算轻松；n=20 时 100 万种，电脑也吃力；n=50 直接放弃。GESP 的 n 可以到几百，必须 DP。
把 8 种组合全列出来（容量 5）：
组合 总重量 总价值 合法？
{} 0 0 ✓
{1} 1 1 ✓
{2} 2 4 ✓
{3} 3 5 ✓
{1,2} 3 5 ✓
{1,3} 4 6 ✓
{2,3} 5 9 ✓ ← 最优
{1,2,3} 6 10 ✗ 超重
一问含义：dp[i][j] = 只考虑前 i 件物品、背包容量为 j 时，能装下的最大总价值。注意"只考虑前 i 件"——第 i+1 件以后的宝贝还没上架，不许偷看。二问转移：站在"第 i 件宝贝面前"，只有两种选择：
两种情况谁大听谁的：dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])（j < w[i] 时只能不拿）。三问边界：第 0 行全 0（没有物品，价值就是 0）——不用特判，数组初始化为 0 即可。
// 0/1 背包（二维版）：w/v 从 1 开始编号 int n = 3, W = 5; int w[] = {0, 1, 2, 3}; int v[] = {0, 1, 4, 5}; vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0)); // 边界：全 0 for (int i = 1; i <= n; i++) { for (int j = 0; j <= W; j++) { dp[i][j] = dp[i - 1][j]; // 不拿第 i 件 if (j >= w[i]) // 放得下才考虑拿 dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]); // 拿第 i 件 } } printf("最大价值: %d\n", dp[n][W]); // 9
抽查两个格子：dp[2][2] = max(dp[1][2]=1, dp[1][0]+4=4) = 4（只拿物品 2）；dp[3][4] = max(dp[2][4]=5, dp[2][1]+5 = 1+5 = 6) = 6（拿物品 1+3，重 4 价 6）。最后一格 dp[3][5] = max(5, dp[2][2]+5 = 4+5 = 9) = 9（物品 2+3）。
观察转移：dp[i][j] 只依赖 dp[i-1][*] 这一行——那一行就够，把"第 i 件"这轮更新直接叠在旧数组上：`dp[j] = max(dp[j], dp[j - w[i]] + v[i])`。但 j 必须倒着填（W → w[i]）。道理：倒着走时，dp[j-w[i]] 还是上一轮（没含第 i 件）的值——第 i 件只用了一次；正着走，dp[j-w[i]] 可能已经被本轮更新过，等于把第 i 件装了两遍。
用物品 2（w=2, v=4）实测。此时 dp（处理完物品 1 后）= [0, 1, 1, 1, 1, 1]：
// 正着填（错）：j = 2,3,4,5 j=2: dp[2] = max(1, dp[0]+4) = 4 j=3: dp[3] = max(1, dp[1]+4) = 5 j=4: dp[4] = max(1, dp[2]+4) = 8 // ← dp[2] 已含物品 2！等于拿了两次 j=5: dp[5] = max(1, dp[3]+4) = 9 // ← 同样拿重了 // 倒着填（对）：j = 5,4,3,2 j=5: dp[5] = max(1, dp[3]+4) = 5 j=4: dp[4] = max(1, dp[2]+4) = 5 // dp[2] 还是旧值 1，只拿了一次 j=3: dp[3] = max(1, dp[1]+4) = 5 j=2: dp[2] = max(1, dp[0]+4) = 4
正填 dp[4] = 8（物品 2 装了两遍：4+4），倒填 dp[4] = 5 ✓（物品 1+2：1+4）。同一件宝贝"分身"了，价值自然虚高。
同一道题写两版：二维（好懂）+ 一维（省空间），答案必须一致。
// 0/1 背包：二维 + 一维 #include <bits/stdc++.h> using namespace std; int main() { int n = 3, W = 5; int w[] = {0, 1, 2, 3}; int v[] = {0, 1, 4, 5}; // 版本 1：二维 vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0)); for (int i = 1; i <= n; i++) for (int j = 0; j <= W; j++) { dp[i][j] = dp[i - 1][j]; if (j >= w[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]); } printf("二维: %d\n", dp[n][W]); // 9 // 版本 2：一维（容量倒序） vector<int> f(W + 1, 0); for (int i = 1; i <= n; i++) for (int j = W; j >= w[i]; j--) // 倒序！ f[j] = max(f[j], f[j - w[i]] + v[i]); printf("一维: %d\n", f[W]); // 9（一致） return 0; }
j >= w[i] 且递减，写成 j++ 正序就变成完全背包（同件拿多次）。② 一维数组全 0 初始化即可（容量 0 价值 0，边界天然成立）。③ 要输出"拿了哪些物品"得另存选择（从 dp[n][W] 往回追），一维滚动后追不回。