完全背包状态转移方程为 dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，内层 j 需升序遍历 weight[i] 到 W；与 0-1 背包区别在于物品可重复使用，故正向遍历确保多次选取。
完全背包问题的状态转移方程怎么写
完全背包和0-1背包的核心区别在于：每个物品可以无限次使用。因此状态转移时，dp[j] 不仅能从 dp[j - weight[i]] 转移来，还要考虑「已经选过第 i 个物品」的情况——也就是从 dp[j - weight[i]] 再加一个，所以必须用正向遍历容量。
正确写法是：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，且内层循环 j 从 weight[i] 到 W（背包总容量）升序遍历。
常见错误是沿用0-1背包的逆序遍历，结果变成只能选一次；或者把 i 和 j 循环顺序写反，导致逻辑错乱。
C++中一维数组实现要注意哪些边界
用一维 vector<int> dp(W + 1, 0)</int> 实现最简洁，但初始化和更新顺序必须严格：
立即学习“C++免费学习笔记（深入）”；
-
dp[0]初始化为 0 是安全的，其余位置也设为 0（求最大价值，非必要不设负无穷） - 外层循环遍历物品
i（0 到n-1），内层循环j从weight[i]到W，不可颠倒 - 若题目要求「恰好装满」，则除
dp[0]外，其余初始化为INT_MIN，并在更新时加判断：if (dp[j - weight[i]] != INT_MIN) - 注意
weight[i]为 0 的情况，会导致无限循环或未定义行为，需提前过滤
如何输出具体选了哪些物品
一维 dp 数组无法直接还原路径，必须额外维护一个选择记录。常用做法是用二维布尔数组 chosen[i][j]，但空间大；更省空间的方式是用一维数组 last[i] 记录达到 dp[j] 时最后加入的物品编号，或用 from[j] 记录前一个容量位置。
实际还原时，从 dp[W] 开始倒推：
- 若
dp[j] == dp[j - weight[i]] + value[i]，说明第 i 个物品被使用（需在更新时同步记录） - 推荐在更新
dp[j]时，同步更新parent[j] = j - weight[i]和item[j] = i - 注意同一个物品可能被多次选取，还原时要循环减去
weight[i]直到不能减为止
性能与数据范围不匹配时怎么调
当 W 达到 1e5 甚至更大，而物品数量 n 很小（比如 ≤ 100），标准 O(nW) 解法会超时或爆内存。这时要考虑优化：
- 若所有
weight[i]都较大，可尝试「二进制拆分 + 0-1背包」，但完全背包不适用；正确方向是「单调队列优化」，将内层复杂度降到 O(W) 总体——适用于价值随容量线性变化的场景 - 更实用的是剪枝：先按单位价值排序，优先处理高性价比物品；对相同重量不同价值的物品，只保留最大价值的那个
- 如果
value[i]很小（如 ≤ 1000），可交换状态定义：令f[v]表示获得价值 v 所需最小重量，转为 O(n × total_value) 求解
别忽略 int 溢出风险——dp 数组建议用 long long，尤其在价值累加或 W 很大时。
