动态规划解决背包问题（0-1背包）

题目描述
0-1背包问题是一个经典的动态规划问题：给定一个容量为 C 的背包和 N 个物品，每个物品有重量 w[i] 和价值 v[i]。每个物品只能选择装入（1）或不装入（0），要求选择物品装入背包，使得在总重量不超过背包容量的前提下，背包中物品的总价值最大。

解题过程

1. 问题分析

   • 每个物品只有选或不选两种状态，不能分割（区别于分数背包）。
   • 目标是最大化总价值，同时总重量不超过 C。

2. 定义状态

   • 定义二维数组 dp[i][j]：表示考虑前 i 个物品（物品编号从1到N），在背包容量为 j 时能获得的最大价值。
   • 最终答案是 dp[N][C]。

3. 状态转移方程

   • 对于第 i 个物品（重量 w[i]，价值 v[i]）：
     • 如果当前背包容量 j < w[i]，无法装入，则最大价值与考虑前 i-1 个物品时相同：
       dp[i][j] = dp[i-1][j]
     • 如果 j ≥ w[i]，有两种选择：
       1. 不装第 i 个物品：价值为 dp[i-1][j]
       2. 装第 i 个物品：价值为 dp[i-1][j - w[i]] + v[i]（剩余容量 j - w[i] 下前 i-1 个物品的最大价值加上当前物品价值）
       • 取两者最大值：
         dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

4. 初始化

   • 容量为0时 (j=0)，无法装任何物品，价值为0：dp[i][0] = 0
   • 考虑0个物品时 (i=0)，无论容量多大，价值均为0：dp[0][j] = 0

5. 示例推导
   假设物品信息如下（物品从1开始编号）：

   w = [2, 3, 4, 5]  # 重量
   v = [3, 4, 5, 6]  # 价值
   C = 8             # 背包容量
   

   • 初始化 dp[0][j] = 0，dp[i][0] = 0。
   • 填写 dp 表（行：物品i，列：容量j）：
     • i=1（物品1，重2价3）：
       j=1: 容量不足，dp[1][1]=dp[0][1]=0
j≥2: dp[1][j] = max(dp[0][j], dp[0][j-2]+3) = 3
     • i=2（物品2，重3价4）：
       j=2: max(dp[1][2]=3, dp[1][-1]无效) → 3
j=3: max(dp[1][3]=3, dp[1][0]+4=4) → 4
j=5: max(dp[1][5]=3, dp[1][2]+4=7) → 7
     • 最终 dp[4][8] = 10（选择物品2和4，总重3+5=8，价值4+6=10）。

6. 空间优化

   • 观察状态转移方程：dp[i][j] 只依赖于上一行 dp[i-1][...]，因此可压缩为一维数组 dp[j]。
   • 递推时需倒序遍历容量（从 C 到 w[i]），避免覆盖上一轮的状态：
     for j in range(C, w[i]-1, -1): dp[j] = max(dp[j], dp[j - w[i]] + v[i])

7. 复杂度分析

   • 时间复杂度：O(N×C)
   • 空间复杂度：
     • 未优化：O(N×C)
     • 优化后：O(C)