动态规划解决0-1背包问题 问题描述 0-1背包问题是一个经典的组合优化问题：给定一个容量为 \( C \) 的背包和 \( N \) 个物品，每个物品有重量 \( w_ i \) 和价值 \( v_ i \)，要求选择若干物品放入背包，使得总重量不超过背包容量，且总价值最大。其中每个物品只能选择放入（1）或不放入（0），因此称为"0-1背包"。 核心难点 物品不可分割，需通过动态规划避免暴力枚举（时间复杂度为 \( O(2^N) \)）。 步骤1：定义状态与子问题 状态定义 ：设 \( dp[ i][ c ] \) 表示考虑前 \( i \) 个物品，在背包容量为 \( c \) 时能获得的最大价值。 子问题划分 ：将问题分解为逐步处理每个物品，并依赖更小容量的子问题结果。 步骤2：建立状态转移方程 对于第 \( i \) 个物品（重量 \( w_ i \)，价值 \( v_ i \)），有两种选择： 不放入背包 ：最大价值与处理前 \( i-1 \) 个物品时相同，即 \( dp[ i][ c] = dp[ i-1][ c ] \)。 放入背包 （需满足 \( c \geq w_ i \)）：价值为当前物品价值加上剩余容量 \( c-w_ i \) 下的最大价值，即 \( dp[ i][ c] = dp[ i-1][ c-w_ i] + v_ i \)。 综合两种情况，状态转移方程为： \[ dp[ i][ c ] = \begin{cases} \max(dp[ i-1][ c], dp[ i-1][ c-w_ i] + v_ i), & \text{if } c \geq w_ i \\ dp[ i-1][ c], & \text{if } c < w_ i \end{cases} \] 步骤3：初始化边界条件 容量为0时 ：任何物品都无法放入，价值恒为0，即 \( dp[ i][ 0 ] = 0 \)。 无物品时 （\( i=0 \)）：无论容量多大，价值均为0，即 \( dp[ 0][ c ] = 0 \)。 步骤4：确定计算顺序 使用双重循环： 外层循环遍历物品编号 \( i \) 从 1 到 \( N \)。 内层循环遍历背包容量 \( c \) 从 1 到 \( C \)。 确保计算 \( dp[ i][ c] \) 时，所需的 \( dp[ i-1][ c] \) 和 \( dp[ i-1][ c-w_ i ] \) 已被计算。 步骤5：举例演算 假设背包容量 \( C=5 \)，物品列表如下： | 物品 | 重量 \( w_ i \) | 价值 \( v_ i \) | |------|---------------|---------------| | 1 | 2 | 6 | | 2 | 1 | 3 | | 3 | 4 | 8 | | 4 | 3 | 7 | 构建 \( dp \) 表（行：物品编号，列：容量）： 初始化：第0行和第0列全为0。 处理物品1（重量2，价值6） ： \( c=1 \)：容量不足，继承 \( dp[ 0][ 1 ]=0 \)。 \( c=2 \)：\( \max(dp[ 0][ 2], dp[ 0][ 0 ]+6) = \max(0, 6) = 6 \)。 \( c\geq2 \) 时同理，值均为6。 处理物品2（重量1，价值3） ： \( c=1 \)：\( \max(dp[ 1][ 1], dp[ 1][ 0 ]+3) = \max(0, 3)=3 \)。 \( c=2 \)：\( \max(dp[ 1][ 2], dp[ 1][ 1 ]+3) = \max(6, 0+3)=6 \)。 \( c=3 \)：\( \max(6, dp[ 1][ 2 ]+3)=9 \)。 继续计算完所有物品，最终 \( dp[ 4][ 5 ]=13 \)（选择物品2、3、4）。 步骤6：空间优化（滚动数组） 观察状态转移方程：\( dp[ i][ c] \) 仅依赖于上一行 \( dp[ i-1][ \cdot ] \)。 可优化为一维数组 \( dp[ c] \)，内层容量需 倒序遍历 （从 \( C \) 到 \( w_ i \)），避免覆盖未使用的上一行数据。 转移方程简化为： \[ dp[ c] = \max(dp[ c], dp[ c-w_ i] + v_ i) \quad (\text{当 } c \geq w_ i) \] 步骤7：复杂度分析 时间复杂度 ：\( O(N \times C) \)。 空间复杂度 ：未优化时为 \( O(N \times C) \)，优化后为 \( O(C) \)。 总结 0-1背包问题的动态规划解法通过将问题分解为子问题，避免重复计算，核心在于状态定义、转移方程和计算顺序。空间优化技巧能显著降低内存使用，适用于容量较大的场景。