动态规划解背包问题的核心是用嵌套循环实现状态转移：二维dpi表示前i个物品、容量j的最大价值，初始化边界为0；外层遍历物品，内层遍历容量，按能否放入更新状态；一维优化需倒序遍历避免重复选取；完全背包则正序遍历。

动态规划求解背包问题，核心在于把“选或不选”的决策过程转化为可递推的状态更新。状态转移方程不是抽象公式，而是嵌套循环中每一行、每一列实际执行的逻辑判断。下面直接讲清楚怎么用嵌套循环落地实现，聚焦实战要点。

明确状态定义与数组维度

状态 dp[i][j] 表示前 i 个物品、背包容量为 j 时能获得的最大价值。 二维数组更直观：行数为物品数 + 1（第 0 行对应“没物品”），列数为容量 + 1（第 0 列对应“容量为 0”）。 初始化：dp[0][*] = 0，dp[*][0] = 0 —— 没物品或没空间，价值必为 0。

外层遍历物品，内层遍历容量

标准写法是： - 外循环 i 从 1 到 n（对应第 i 个物品，注意数组下标偏移） - 内循环 j 从 0 到 W（背包总容量）

对每个 (i, j)，执行状态转移：

若当前物品重量 w[i−1] > j：放不下 → dp[i][j] = dp[i−1][j]

否则：取两种选择的最大值 → dp[i][j] = max(dp[i−1][j], dp[i−1][j − w[i−1]] + v[i−1])

这个判断必须在内层循环里实时做，不能提前跳过。

空间优化：一维数组倒序遍历

观察发现，dp[i][j] 只依赖 dp[i−1][*]，所以可用一维数组 dp[j] 替代。 关键细节：内层 j 必须从大到小遍历（即 j = W → w[i−1]），否则会重复使用刚更新的值，把 0/1 背包错当成完全背包处理。 例如：

for (int i = 0; i

  for (int j = W; j >= w[i]; j--)

    dp[j] = max(dp[j], dp[j − w[i]] + v[i]);

完全背包的循环差异

如果物品可无限次使用（完全背包），仅需将内层 j 改为从小到大遍历（j = w[i] → W）。 因为 dp[j − w[i]] 此时已是考虑过第 i 个物品的最新值，允许再次加入同一物品。 状态转移式变为：dp[j] = max(dp[j], dp[j − w[i]] + v[i])

最终答案始终是 dp[n][W]（二维）或 dp[W]（一维），代表所有物品、满容量下的最大价值。