0-1背包问题推荐用std::vector实现二维dp，状态dpi表示前i个物品容量w的最大价值，需先遍历物品再遍历容量，初始化dp0和dp*为0，维度为(n+1)×(w+1)，转移方程为dpi=max(dpi-1, dpi-1]+value[i-1])。
0-1背包问题用std::vector实现DP最稳妥
直接上二维DP数组容易越界或初始化出错，推荐用std::vector动态分配空间，避免手动管理内存和边界错误。状态定义为dp[i][w]表示前i个物品、容量为w时的最大价值。
常见错误是把循环顺序写反：必须先遍历物品（外层），再遍历容量（内层），否则会重复使用同一物品（变成完全背包）。初始化时dp[0][*]全为0，dp[*][0]也全为0——容量为0时无法装任何物品。
-
dp维度设为(n+1) × (W+1)，其中n是物品数量，W是背包总容量 - 内层容量循环从
w = weight[i-1]开始向上递推，避免访问负索引 - 转移方程固定为：
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + value[i-1]) - 若只求最大价值（不需路径），可压缩为一维
vector<int> dp(W+1)</int>，但内层循环必须从W到weight[i]倒序遍历
一维DP压缩后dp[w]更新顺序不能错
省空间是一维DP的主要动机，但倒序遍历是硬性要求。正序会导致dp[w - weight[i]]已被本轮更新过，相当于允许多次选同一物品。
比如weight = [2, 3]，W = 5，若正序更新dp[2]后马上用于dp[4]，就等于把第一个物品用了两次。
- 一维写法中，
i从0到n-1，w必须从Wdowntoweight[i] - 初始化
dp全为0，无需额外处理边界 - 最终答案就是
dp[W]，不是max_element——因为容量恰好装满未必最优，DP本身已覆盖所有≤W的可能
求具体方案时得回溯dp表，不能只靠一维数组
一维dp只存最终值，丢掉了决策路径。要输出选了哪些物品，必须保留二维表，或额外记录choice[i][w]布尔值。
回溯逻辑简单：从dp[n][W]出发，若dp[i][w] != dp[i-1][w]，说明第i-1个物品被选中，然后跳转到dp[i-1][w - weight[i-1]]继续判断。
- 回溯起点是
i = n,w = W，终点是i = 0 - 注意索引偏移：物品数组下标从
0开始，dp行号i对应前i个物品 - 如果题目要求“恰好装满”，初始化时除
dp[0][0] = 0外，其余设为INT_MIN，避免无效状态干扰回溯
long long溢出和vector构造参数陷阱
价值总和可能超int范围，尤其当value[i]达1e9、物品数超100时，dp数组必须用long long。另一个隐形坑是vector构造：写vector<long long>(W+1, 0)</long>没问题，但若误写成vector<long long>(W+1)</long>，会默认初始化为0，看似正常，实则依赖未明确定义的行为（C++标准规定默认构造内置类型为未初始化）。
- 务必显式初始化：用
vector<long long>(W+1, 0LL)</long>或vector<long long>(W+1, {})</long> - 输入数据要检查
W是否过大——若W > 1e4，二维DP可能MLE，此时需考虑空间优化或改用DFS+剪枝 - 物品重量为0时需单独处理：若
weight[i] == 0 && value[i] > 0，只要容量≥0就应无条件加入（但实际题中通常保证重量>0）
背包问题真正难的不是状态转移，而是边界条件和数据类型的隐式假设——一个int换成long long，或一个正序改成倒序，就能让结果全错。动手前先盯住这三个点：维度、顺序、初始化值。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
