二维dp易爆内存，因n=10⁴、W=10⁵时需4GB空间；实用解法是降维为一维dp[w]并从右往左更新，避免重复选取同一物品。
为什么直接用二维 dp[i][w] 容易爆内存
当物品数量 n 达到 10⁴、背包容量 W 达到 10⁵ 时，dp[n+1][W+1] 数组会占用约 10⁹ 个 int（4GB），远超一般栈/堆限制。很多初学者卡在这一步——不是逻辑错，是 vector<vector>></vector> 申请失败或运行超时。
真正实用的写法必须降维：只保留一维 dp[w]，表示「容量为 w 时能装下的最大价值」，并**从右往左更新**。
- 错误写法：
for (int w = 0; w → 会重复使用刚更新的值，变成完全背包 - 正确顺序：
for (int w = W; w >= weight[i]; --w)→ 确保dp[w - weight[i]]还是上一轮（未选第i件）的状态 - 初始化：
dp[0..W]全为 0，表示没放任何物品时价值为 0
dp[w] 的状态转移为什么不能正向遍历
假设当前处理第 i 件物品（重量 w_i，价值 v_i），若正向遍历：
for (int w = w_i; w <= W; ++w) {
dp[w] = max(dp[w], dp[w - w_i] + v_i);
}当 w = w_i 时，dp[w_i] 被更新为 v_i；紧接着 w = 2*w_i 时，dp[2*w_i] 会用到这个新值，相当于把第 i 件物品用了两次 —— 这是完全背包行为，违反 0-1 约束。
立即学习“C++免费学习笔记（深入）”；
反向遍历时，dp[w - w_i] 永远来自上一轮状态，保证每件物品最多选一次。
如何还原具体选了哪些物品
仅靠一维 dp 数组无法回溯路径，必须额外记录决策信息。最轻量做法是用布尔数组 chosen[i][w]，但空间又回去了。更实用的是：**在填表时同步维护一个 from[w] 数组，记录容量 w 的最优值是否由第 i 件物品转移而来**。
- 声明：
vector<bool> from(W + 1); // from[w] == true 表示 w 处发生了选择</bool> - 更新时：
if (dp[w] - 回溯：
w = W开始，若from[w]为真，则选第i件，w -= w_i，继续向前；否则跳过该物品
注意：这个 from 数组需在每轮 i 内独立维护（即每次循环前重置），或改用二维标记（空间换逻辑清晰）。
边界和性能容易被忽略的点
实际编码时这几个细节常导致 WA 或 TLE：
-
weight[i]为 0 时，w >= weight[i]恒成立，但除零或无限循环风险不存在，不过逻辑上应直接跳过或特殊处理（0 重物品可无条件选） -
W很大但所有weight[i]都很小？考虑用「以价值为状态」的反向 DP（dp[v]表示达成价值v的最小重量），适用于sum(value) ≤ 10⁴场景 - 使用
vector<int> dp(W + 1)</int>时，确保W ≥ 0，否则vector构造崩溃；加一句if (W - 输入含负价值？标准 0-1 背包不支持，需先过滤或转为其他模型
一维 DP 的核心就两行：反向循环 + 原地更新。其它都是围绕它补全的工程细节。
