背包问题（0-1背包）的动态规划解法 问题描述 0-1背包问题是一个经典的组合优化问题：给定一组物品，每个物品有重量 \( w_ i \) 和价值 \( v_ i \)，以及一个容量为 \( W \) 的背包。要求选择物品放入背包，使得背包中物品的总重量不超过 \( W \)，且总价值最大。其中每个物品只能选择放入（1）或不放入（0），因此称为“0-1背包”。 解题过程 问题分析 暴力解法：枚举所有物品的子集（共 \( 2^n \) 种可能），检查重量是否超限，并计算最大价值。时间复杂度为 \( O(2^n) \)，不可行。 关键特性：问题具有最优子结构。若已知前 \( i-1 \) 个物品在容量 \( j \) 下的最大价值，则前 \( i \) 个物品的解可通过第 \( i \) 个物品是否放入来递推。 定义状态 设 \( dp[ i][ j ] \) 表示考虑前 \( i \) 个物品（物品编号从1到i），在背包容量为 \( j \) 时能获得的最大价值。 状态转移方程 若第 \( i \) 个物品的重量 \( w_ i > j \)（放不下），则： \[ dp[ i][ j] = dp[ i-1][ j ] \] 若 \( w_ i \leq j \)（能放下），则有两种选择： 不放入：价值为 \( dp[ i-1][ j ] \) 放入：价值为 \( dp[ i-1][ j - w_ i] + v_ i \) 取两者最大值： \[ dp[ i][ j] = \max(dp[ i-1][ j], dp[ i-1][ j - w_ i] + v_ i) \] 初始化 容量为0时（\( j=0 \)）：任何物品都无法放入，\( dp[ i][ 0 ] = 0 \) 物品数为0时（\( i=0 \)）：无物品可选，\( dp[ 0][ j ] = 0 \) 填表示例 假设物品列表：\( (w, v) = [ (2, 3), (3, 4), (4, 5) ] \)，背包容量 \( W=5 \)。 填写 \( dp \) 表如下（行：物品索引，列：容量0~5）： | i\j | 0 | 1 | 2 | 3 | 4 | 5 | |-----|---|---|---|---|---|---| | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 0 | 0 | 3 | 3 | 3 | 3 | | 2 | 0 | 0 | 3 | 4 | 4 | 7 | | 3 | 0 | 0 | 3 | 4 | 5 | 7 | 第1行（仅物品1）：容量≥2时可放入，价值为3。 第2行（加入物品2）： \( j=5 \)：不放入得3，放入需占用容量3，剩余容量2的价值3，总价值4+3=7，取max=7。 第3行（加入物品3）： \( j=4 \)：不放入得4，放入需占用容量4，剩余容量0的价值0，总价值5，取max=5。 空间优化 观察转移方程：\( dp[ i][ j] \) 只依赖于上一行 \( dp[ i-1][ \cdot ] \)。 可优化为一维数组 \( dp[ j ] \)，但需从右向左更新（避免覆盖上一行状态）： \[ \text{for } j = W \text{ down to } w_ i: \quad dp[ j] = \max(dp[ j], dp[ j - w_ i] + v_ i) \] 复杂度分析 时间复杂度：\( O(n \times W) \)（n为物品数） 空间复杂度：优化后为 \( O(W) \) 总结 0-1背包问题通过动态规划将指数复杂度优化为伪多项式复杂度。核心在于识别最优子结构，定义状态与转移方程，并利用空间优化技巧降低内存占用。