动态规划：0-1背包问题空间复杂度优化详解

题目描述
0-1背包问题是经典的动态规划问题：给定n个物品，每个物品有重量w_i和价值v_i，以及一个容量为C的背包。每个物品要么完整放入（1），要么不放入（0）。目标是选择若干物品放入背包，使得总重量不超过C，且总价值最大。本专题将深入讲解如何将其空间复杂度从O(nC)优化到O(C)。

解题过程

1. 问题定义与基础状态设计
设dp[i][j]表示考虑前i个物品（物品编号从1到i），在背包容量为j时能获得的最大价值。
状态转移方程：
dp[i][j] = max(dp[i-1][j], // 不选第i个物品
dp[i-1][j - w_i] + v_i) // 选第i个物品，要求j >= w_i
基础状态：dp[0][j] = 0 (0个物品价值为0)

这是二维DP表格，空间复杂度O(nC)。

2. 空间优化核心观察
仔细看状态转移方程：dp[i][j]的计算只依赖于上一行（i-1）的数据！
具体来说，dp[i][j]只依赖于dp[i-1][j]和dp[i-1][j-w_i]。这意味着我们不需要存储完整的n行，只需要两行（当前行和上一行）就能完成计算。

3. 滚动数组优化（两行数组）
我们可以用两个一维数组：

• prev[0..C] 表示上一行（i-1）的结果
• curr[0..C] 表示当前行（i）的结果
  计算过程：

prev = [0] * (C+1)  # 初始化第0行
for i in range(1, n+1):
    for j in range(C+1):
        curr[j] = prev[j]  # 不选当前物品
        if j >= w[i-1]:
            curr[j] = max(curr[j], prev[j - w[i-1]] + v[i-1])
    prev, curr = curr, prev  # 交换，当前行变为下一轮的上一行

空间复杂度：O(2C) = O(C)

4. 进一步优化到单行数组（倒序更新）
关键洞察：如果我们用单个数组dp[0..C]，并从后往前更新，可以避免覆盖还需要使用的"上一行"数据。

为什么必须倒序？

• 当我们计算dp[j]时（考虑前i个物品），需要用到dp[j]（相当于上一行的dp[i-1][j]）和dp[j-w_i]（相当于上一行的dp[i-1][j-w_i]）。
• 如果从C到0逆序更新：
  • 当我们更新dp[j]时，dp[j]还是上一轮（i-1）的值
  • dp[j-w_i]也是上一轮（i-1）的值（因为j-w_i < j，我们还没更新到它）
• 如果从0到C正序更新：
  • 当我们更新dp[j]时，dp[j-w_i]可能已经被更新为当前轮（i）的值，这会导致错误

单数组实现：

def knapsack_01_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for i in range(n):  # 考虑每个物品
        w, v = weights[i], values[i]
        # 关键：从后往前遍历容量
        for j in range(capacity, w-1, -1):
            # dp[j] 不选当前物品（保持原值）
            # dp[j-w] + v 选当前物品
            dp[j] = max(dp[j], dp[j-w] + v)
    
    return dp[capacity]

5. 算法步骤分解（以示例说明）
示例：n=3, C=4, weights=[1,3,4], values=[15,20,30]

初始化：dp = [0,0,0,0,0] (容量0~4)

物品1 (w=1, v=15):

• j=4: dp[4] = max(dp[4]=0, dp[3]=0+15) = 15
• j=3: dp[3] = max(0, dp[2]=0+15) = 15
• j=2: dp[2] = max(0, dp[1]=0+15) = 15
• j=1: dp[1] = max(0, dp[0]=0+15) = 15
• j=0: 跳过 (j < w)
  dp变为: [0,15,15,15,15]

物品2 (w=3, v=20):

• j=4: dp[4] = max(15, dp[1]=15+20) = 35
• j=3: dp[3] = max(15, dp[0]=0+20) = 20
• j=2: 跳过 (j<3)
  dp变为: [0,15,15,20,35]

物品3 (w=4, v=30):

• j=4: dp[4] = max(35, dp[0]=0+30) = 35
  dp最终: [0,15,15,20,35]

最大价值为35。

6. 时间与空间复杂度分析

• 时间复杂度：O(nC)，与二维DP相同
• 空间复杂度：O(C)，相比二维DP的O(nC)是显著优化
• 当C很大时，可能仍会占用较多内存，但对于大多数实际问题，C通常在可接受范围

7. 优化方案的适用性与限制

• 适用场景：标准的0-1背包问题
• 不适用场景：
  • 需要回溯具体选择了哪些物品（单数组丢失了决策路径信息）
  • 完全背包问题（物品无限个）需要正序更新
  • 多重背包问题需要特殊处理
• 如果需要具体方案，可以用二维DP或额外记录决策

8. 常见变体与扩展

• 恰好装满背包：初始化dp[0]=0, dp[1..C]=-∞
• 方案计数：dp[j]表示方案数，转移时用加法
• 最优方案回溯：用二维DP或额外数组记录选择

总结
0-1背包问题的空间优化核心是认识到状态转移的"无后效性"和"单向依赖性"，通过倒序更新单数组，既保留了子问题的解，又避免了数据覆盖。这是动态规划空间优化的经典范例，在竞赛和面试中经常出现。