<p>完全背包一维状态转移方程为 dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，内层 j 正向遍历，因需复用已更新的 dp[j - weight[i]] 实现物品无限选取；二维对应 dpi = max(dpi-1, dpi] + value[i])。</p>
完全背包的状态转移方程长什么样
标准写法是：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，注意这里是一维数组、且内层循环正向遍历（j 从 weight[i] 到 capacity）。和 0-1 背包只差一个方向：0-1 背包必须倒序，否则会重复使用物品；而完全背包正序，才允许同一物品被多次选中。
为什么一维数组要正向遍历
因为 dp[j - weight[i]] 在正序时可能已经更新过——它代表「已考虑过第 i 个物品的更小容量状态」，所以当前这次更新就等效于「在已有选择基础上再拿一个 i」。这正是“无限数量”的体现。
常见错误现象：
- 误用 0-1 背包的倒序逻辑，导致每个物品最多用一次
- 把二维写法直接平移成一维但没改遍历方向，结果答案偏小
- 初始化错误：要求恰好装满时，
dp[0] = 0，其余设为负无穷；不要求恰好时，全部初始化为 0
二维写法怎么对应到一维
二维状态是 dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]] + value[i]) —— 注意第二项是 dp[i][...]，不是 dp[i-1][...]，说明第 i 个物品可以重复参与转移。压缩成一维后，正向遍历才能让 dp[j-weight[i]] 保留本轮更新过的值。
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
实操建议：
- 调试时先写二维版本验证逻辑，再降维
- 检查循环嵌套顺序：外层是物品（
i），内层是容量（j正向） - 若题目要求「最少硬币数」而非最大价值，把
max换成min，并初始化为大整数（如INT_MAX/2防溢出）
容易被忽略的边界和类型细节
重量和价值数组下标是否从 0 开始、capacity 是否可能为 0、weight[i] 是否可能为 0（会导致无限循环）——这些都会让 dp[j - weight[i]] 访问越界或陷入死循环。
务必加保护：
- 循环内判断
if (weight[i] 再更新 - 用
size_t时小心j - weight[i]下溢（转成有符号比较更安全） - 如果
weight[i] == 0且value[i] > 0，问题无解（可无限增益），应提前返回
实际写的时候，别光背方程，盯着“哪个状态依赖哪个状态”画两行小表格，比记公式管用。
