二维dp易爆内存，因n=10⁴、W=10⁵时需4GB空间；实用解法是降维为一维dp[w]并从右往左更新，避免重复选取同一物品。
为什么直接用二维 dp[i][w] 容易爆内存
当物品数量 n 达到 10⁴、背包容量 W 达到 10⁵ 时，dp[n+1][W+1] 数组会占用约 10⁹ 个 int（4GB），远超一般栈/堆限制。很多初学者卡在这一步——不是逻辑错，是 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），若正向遍历：
w = w_i
- 声明：
vectorfrom(W + 1); // from[w] == true 表示 w 处发生了选择 - 更新时：
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时，确保dp(W + 1) W ≥ 0，否则vector构造崩溃；加一句if (W - 输入含负价值？标准 0-1 背包不支持，需先过滤或转为其他模型
一维 DP 的核心就两行：反向循环 + 原地更新。其它都是围绕它补全的工程细节。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
