如果 j < w_i （当前背包容量 j 小于物品 i 的重量，根本装不下）：
    dp[i][j] = dp[i-1][j] // 只能选择不装
否则（当前背包容量可以装下物品 i）：
    dp[i][j] = max( dp[i-1][j],         // 选择一：不装物品 i
                    v_i + dp[i-1][j - w_i] // 选择二：装物品 i
                  )

动态规划解决背包问题 背包问题是动态规划领域的经典问题，它描述的是：有一个容量为 C 的背包，和 n 件物品。每件物品 i 有对应的重量 w_ i 和价值 v_ i。我们的目标是从这些物品中选择一些装入背包，使得在不超过背包容量的前提下，装入物品的总价值最大。 这是一个典型的组合优化问题，我们可以通过循序渐进的动态规划思路来解决它。 第一步：定义状态 动态规划的核心在于定义状态，并找到状态之间的转移关系。我们定义这样一个状态： dp[i][j] 表示一个子问题的解： 考虑前 i 件物品（物品编号从1到i），在背包容量为 j 的情况下，能够获得的最大价值 。 这里， i 的取值范围是 0 <= i <= n （考虑0件物品到考虑全部n件物品）， j 的取值范围是 0 <= j <= C （背包容量从0到最大容量C）。 这个二维数组 dp 就是我们最终要填满的表格。 第二步：确定初始状态 在开始考虑任何物品之前，或者背包容量为0时，我们能获得的价值显然是0。 第一行（i=0） ：当不考虑任何物品时，无论背包容量 j 有多大，最大价值都是0。即 dp[0][j] = 0 。 第一列（j=0） ：当背包容量为0时，无论考虑哪些物品，都无法装入任何物品，最大价值也是0。即 dp[i][0] = 0 。 第三步：建立状态转移方程 这是最关键的一步。我们现在要思考，如何根据已知的子问题解，来推导出 dp[i][j] 。 对于第 i 件物品，我们只有两种选择： 装入背包 或者 不装入背包 。 不装入第 i 件物品 ： 如果我们决定不装第 i 件物品，那么问题就退化成了“考虑前 i-1 件物品，在容量为 j 的背包下的最大价值”。 这个解我们已经计算过了，就是 dp[i-1][j] 。 装入第 i 件物品 ： 如果我们决定装入第 i 件物品，那么首先需要保证背包的剩余容量能够装下它，即 j >= w_i 。 如果装得下，那么装入它之后，背包的剩余容量就变为 j - w_i 。 此时，我们的总价值就等于 第 i 件物品的价值 v_ i 加上 “考虑前 i-1 件物品，在剩余容量 j - w_i 的背包下的最大价值” 。 这个解就是 v_i + dp[i-1][j - w_i] 。 我们的目标是最大化总价值。因此， dp[i][j] 应该取这两种选择中的最大值。 综合起来，状态转移方程如下： 第四步：计算顺序与填表 我们已经有了初始状态和状态转移方程，现在需要确定填表的顺序。观察状态转移方程，要计算 dp[i][j] ，我们需要用到 dp[i-1][j] （正上方格子）和 dp[i-1][j - w_i] （左上方某个格子）。 这意味着，我们必须 从上到下（i 从 1 递增到 n），从左到右（j 从 1 递增到 C） 地填充整个 dp 表格。这样才能保证在计算每个格子时，它所需要的前置状态都已经被计算出来了。 第五步：举例说明 假设背包容量 C=5，物品信息如下： | 物品 i | 重量 w_ i | 价值 v_ i | | :---- | :------- | :------- | | 1 | 2 | 6 | | 2 | 1 | 3 | | 3 | 4 | 8 | | 4 | 3 | 7 | 我们初始化一个 dp[5][6] 的表格（因为 i 从0到4，j 从0到5）。 初始化 (i=0)： dp[0][j] = 0 for all j. 开始填表： i=1（考虑物品1，重量2，价值6） j=0,1: 容量小于2，装不下。 dp[1][0]=0 , dp[1][1]=dp[0][1]=0 j=2,3,4,5: 容量足够。 dp[1][j] = max(dp[0][j], 6+dp[0][j-2]) = max(0, 6+0) = 6 i=2（考虑物品1和2，物品2重量1，价值3） j=0: 容量0， dp[2][0]=0 j=1: 只能装物品2。 dp[2][1] = max(dp[1][1], 3+dp[1][0]) = max(0, 3+0)=3 j=2: 可装物品1或2。 dp[2][2] = max(dp[1][2], 3+dp[1][1]) = max(6, 3+0)=6 j=3: dp[2][3] = max(dp[1][3], 3+dp[1][2]) = max(6, 3+6)=9 j=4,5: 同理计算。 i=3, i=4... 继续按照状态转移方程填充整个表格。 最终填完的表格 dp[i][j] 如下（你可以尝试自己填一下以加深理解）： | i\j | 0 | 1 | 2 | 3 | 4 | 5 | | :-- | :-: | :-: | :-: | :-: | :-: | :-: | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 0 | 0 | 6 | 6 | 6 | 6 | | 2 | 0 | 3 | 6 | 9 | 9 | 9 | | 3 | 0 | 3 | 6 | 9 | 9 | 11 | | 4 | 0 | 3 | 6 | 9 | 10 | 13 | 表格右下角的值 dp[4][5] = 13 就是我们的最终答案：最大价值为13。 第六步：空间优化（滚动数组） 观察状态转移方程， dp[i][...] 只依赖于 dp[i-1][...] 。这意味着我们并不需要存储整个 n x C 的二维数组，而只需要保存 两行 （当前行和上一行）就足够了。计算完第 i 行后，第 i-1 行的数据就不再需要，可以用第 i 行的数据覆盖它。这样可以将空间复杂度从 O(n* C) 降低到 O(C)。这是一种常见的优化技巧，称为“滚动数组”。 总结 解决背包问题的动态规划方法，其核心步骤是： 定义状态 dp[i][j] 。 确定初始状态 （第一行和第一列）。 建立状态转移方程 ，分析物品“装”与“不装”两种选择。 确定计算顺序 ，保证前置状态已计算。 填表计算 ，最终答案在 dp[n][C] 。 考虑空间优化 。 这个方法（0-1背包问题）是许多复杂背包问题（如完全背包、多重背包）的基础，理解它至关重要。