二维dpi易爆内存因n=1000、w=10000时需约40mb；优化用一维dp，倒序遍历w确保依赖上轮状态，初始化dp[0..w]=0，仅求最大价值时足够，求方案需保留二维或额外记录路径。
为什么直接用二维 dp[i][w] 容易爆内存？
当物品数量 n 达到 1000、背包容量 W 达到 10000 时，dp[n+1][W+1] 就需要约 1000 × 10000 = 10⁷ 个 int，即 40MB 内存——在某些 OJ 或嵌入式环境里已经超限。这不是理论问题，是真实跑不过的卡点。 实际写法必须考虑空间优化。
怎么把二维 DP 压成一维？关键在遍历顺序
核心原则：更新 dp[w] 时，依赖的是上一轮（i−1）的 dp[w] 和 dp[w - weight[i]]。如果正向遍历 w，dp[w - weight[i]] 可能已被本轮覆盖，导致错误复用新值。
正确做法是倒序遍历：
for (int i = 0; i = weight[i]; w--) {
dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
}
}
-
dp数组长度为W+1，初始化为 0 - 外层循环按物品顺序处理，内层从
W往weight[i]倒推 - 倒序确保每次用的
dp[w - weight[i]]是上一轮结果
初始化和边界条件常被忽略的细节
初始状态不是“全设 0”就万事大吉——它隐含了“前 0 个物品时，任何容量下最大价值为 0”，这没问题；但如果你要输出具体选了哪些物品，就不能只靠一维数组回溯。
- 若只需最大价值，一维
dp[W]足够 - 若需方案（哪些物品被选），必须保留二维数组，或额外用
choice[i][w]记录决策，或倒推时用辅助数组记录路径 - 注意
weight[i]为 0 的情况：会导致无限循环或除零，实际输入应提前过滤 -
value[i]为负数时，max逻辑依然成立，但语义已偏离经典 0-1 背包，需确认题意
测试时最容易暴露的三个 bug
写完别急着交，先手动过这几组小数据：
-
n=1, weight=[2], value=[3], W=1→ 答案应为 0（装不下） -
n=2, weight=[1,2], value=[1,2], W=2→ 答案应为 2（选第二个，不是 1+2=3 —— 注意这是 0-1 背包，不是完全背包） -
n=3, weight=[3,2,1], value=[6,4,2], W=4→ 正确答案是 8（选 weight=3+1，value=6+2）
很多错源于混淆了“当前物品索引”和“容量下标”，或者把 w - weight[i] 写成 w - weight[i-1] 这类偏移错误。调试时打印中间 dp 数组前几轮，比瞎猜快得多。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
