背包问题的动态规划解法 题目描述 背包问题是一个经典的组合优化问题：给定一组物品，每个物品有重量和价值，在不超过背包承重的前提下，选择物品使得总价值最大。形式化描述为： 背包容量：\( W \) 物品数量：\( n \) 第 \( i \) 个物品的重量：\( w_ i \)，价值：\( v_ i \) 目标：选择物品子集，满足 \( \sum w_ i \leq W \)，且最大化 \( \sum v_ i \)。 解题思路 动态规划通过将问题分解为子问题来求解。定义状态和状态转移方程是关键。 步骤1：定义状态 设 \( dp[ i][ j ] \) 表示考虑前 \( i \) 个物品（物品编号从1到i），在背包容量为 \( j \) 时能获得的最大价值。 步骤2：初始化 当物品数量为0（\( i=0 \)）或背包容量为0（\( j=0 \)）时，最大价值为0： \( dp[ 0][ j] = 0 \)，\( dp[ i][ 0 ] = 0 \)。 步骤3：状态转移方程 对于每个物品 \( i \) 和每种容量 \( j \)： 若当前物品重量 \( w_ i > j \) ：无法放入，继承前 \( i-1 \) 个物品的结果： \( dp[ i][ j] = dp[ i-1][ j ] \)。 若 \( w_ i \leq j \) ：有两种选择： 不放入 ：价值为 \( dp[ i-1][ j ] \)。 放入 ：价值为 \( dp[ i-1][ j - w_ i] + v_ i \)（剩余容量 \( j-w_ i \) 下的最大价值加上当前物品价值）。 取两者最大值： \( dp[ i][ j] = \max(dp[ i-1][ j], dp[ i-1][ j - w_ i] + v_ i) \)。 步骤4：填表计算 按顺序遍历 \( i \) 从1到 \( n \)，\( j \) 从1到 \( W \)，填充二维数组 \( dp \)。最终答案在 \( dp[ n][ W ] \)。 步骤5：空间优化 由于 \( dp[ i][ j] \) 只依赖于上一行 \( i-1 \) 的数据，可将二维数组优化为一维数组 \( dp[ j ] \)： 倒序遍历 \( j \) 从 \( W \) 到 \( w_ i \)（避免覆盖上一行数据）： \( dp[ j] = \max(dp[ j], dp[ j - w_ i] + v_ i) \)。 示例演示 假设物品信息如下（\( n=4, W=8 \)）： | 物品 | 重量 \( w_ i \) | 价值 \( v_ i \) | |------|---------------|---------------| | 1 | 2 | 3 | | 2 | 3 | 4 | | 3 | 4 | 5 | | 4 | 5 | 6 | 优化后的一维DP计算过程 （初始 \( dp[ j ] = 0 \)）： 物品1（重量2，价值3） ： \( j=8 \) 到 \( 2 \)：\( dp[ 8] = \max(0, dp[ 6]+3)=3 \)，同理更新 \( dp[ 7] \) 到 \( dp[ 2 ] \) 为3。 物品2（重量3，价值4） ： \( j=8 \)：\( dp[ 8] = \max(3, dp[ 5 ]+4)=7 \)（放入物品2和1）。 类似更新其他容量。 物品3和4 ：继续同理更新，最终 \( dp[ 8 ] = 10 \)（选择物品2和4，重量3+5=8，价值4+6=10）。 关键点总结 动态规划的核心是子问题重叠和最优子结构。 空间优化需注意遍历顺序，避免重复计算。 时间复杂度：\( O(nW) \)，空间复杂度：\( O(W) \)。