0-1背包状态转移方程为dpi = max(dpi-1, dpi-1] + value[i])，要求w≥weight[i]；一维优化需倒序遍历容量以防重复选取；求最大价值初始化全0，求恰好装满则dp[0]=0、其余为-inf。
背包问题的状态转移方程怎么写对
0-1 背包最核心的判断是：dp[i][w] 表示「前 i 个物品、容量上限为 w 时能获得的最大价值」。状态转移必须严格按这个定义推导，否则后续所有计算都会错。
关键逻辑是：对第 i 个物品（索引从 1 开始），只有两种选择——不选，或选（前提是 w >= weight[i]）：
- 不选：
dp[i][w] = dp[i-1][w] - 选：
dp[i][w] = dp[i-1][w - weight[i]] + value[i]
二者取大：
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]);注意：
w - weight[i] 必须 ≥ 0，否则不能选，只能取前者。
一维数组优化时为什么必须倒序遍历容量
用 dp[w] 压缩空间后，若正序遍历 w（从 0 到 W），会导致同一个物品被重复使用多次——这实际变成了完全背包，不是 0-1 背包。
立即学习“C++免费学习笔记（深入）”；
倒序（从 W 到 weight[i]）确保每次更新 dp[w] 时，所依赖的 dp[w - weight[i]] 还是上一轮（即未考虑当前物品）的值。
错误写法（正序）：
for (int w = weight[i]; w <= W; w++) { ... }正确写法：for (int w = W; w >= weight[i]; w--) { dp[w] = max(dp[w], dp[w - weight[i]] + value[i]); }
初始化 dp 数组该填什么值
求「最大价值」时，dp 全部初始化为 0 即可——因为不选任何物品价值就是 0，且所有状态都是从合法子状态转移而来。
但如果是求「恰好装满背包时的最大价值」，则需区分：
– dp[0] = 0（容量为 0 时，不选物品刚好满足）
– 其余 dp[w] = -INF（表示不可达）
这样能保证最终 dp[W] > 0 时，一定存在一种方案恰好装满。
常见错误：把「恰好装满」和「不超过容量」混用同一套初始化，导致答案偏大或为 0。
C++ 实现要注意的边界与类型细节
数组下标从 0 开始，但物品编号习惯从 1 开始，容易错位。建议统一用 0-indexed 物品：weight[i] 对应第 i 个物品（i ∈ [0, n)）。
-
weight和value数组用vector<int></int>，避免越界访问 - 容量
W很大时（如 1e9），不能开dp[W+1]—— 此时需换思路（如「价值为状态，求最小重量」） - 若价值总和不大（如 ≤ 1e4），可设
dp[v] = 最小所需重量，状态数大幅下降 - 所有中间计算用
int要防溢出；必要时用long long，尤其在状态转移中加法较多时
动态规划没有银弹，状态定义一旦定错，整个转移就崩。背包问题的“难”不在代码长度，而在第一行 dp 定义是否真正匹配题意——多读两遍题目，比多调十分钟代码更省时间。
