推荐一维dp数组实现01背包，因其空间复杂度从O(N×W)降至O(W)，且倒序遍历w可避免重复选取同一物品；初始化全为0，若要求恰好装满则dp[0]=0、其余为INT_MIN。
01 背包问题用 std::vector 一维数组实现最稳妥，别直接套二维模板——空间浪费、边界易错、初始化麻烦。
为什么推荐一维 dp 数组而不是二维？
二维 dp[i][w] 看起来直观，但实际编码中容易混淆 i 和 w 的循环顺序，且每次只依赖上一行，空间完全可压缩。一维 dp[w] 不仅省空间（从 O(N×W) 到 O(W)），还能强制你理解“滚动更新”的本质。
- 错误常见于：内层循环正向遍历
w，导致同一个物品被重复选多次（变成完全背包） - 正确做法：内层循环必须倒序从
W到weight[i]，确保dp[w]更新时用的是未被当前物品影响的旧值 - 初始化：全部设为
0即可（表示容量为w时最大价值，初始无物品可选）
std::vector<int> dp(W + 1)</int> 的初始化和转移怎么写？
假设 weights = {2, 1, 3}，values = {2, 3, 4}，背包容量 W = 4：
std::vector<int> dp(W + 1, 0);
for (int i = 0; i < weights.size(); ++i) {
for (int w = W; w >= weights[i]; --w) {
dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
}
}
// 最终答案在 dp[W]
-
dp[w]始终表示「考虑前i个物品时，容量为w的最大价值」 - 倒序保证
dp[w - weights[i]]是上一轮（即没选第i个物品时）的值 - 如果题目要求恰好装满背包，初始化需改为：
dp[0] = 0，其余为INT_MIN，避免无效状态转移
遇到负权值或浮点重量怎么办？
标准 01 背包要求重量和价值为非负整数。一旦出现负权值，dp[w] 的定义失效，无法用此方法；浮点重量则不能作为数组下标——这两种情况都得换思路：
立即学习“C++免费学习笔记（深入）”；
- 负价值：可转为「最小化损失」建模，但需重定义状态，不再是经典背包
- 浮点重量：必须离散化或改用记忆化搜索（
std::map<std::pair<int, double>, int>不现实，精度+性能双崩） - 超大容量（如
W = 1e9）：此时应考虑「价值为状态，求最小重量」，把dp[v]定义为达成价值v所需最小重量
真正卡住人的从来不是状态转移方程本身，而是循环方向、初始化语义、以及「容量是否必须装满」这个条件对初值的隐式要求——这三个点不核对清楚，dp 数组跑出来的结果看起来合理，实则全是错的。
