0-1背包问题是动态规划中的经典问题，它要求在给定背包容量和一组物品（每个物品有重量和价值）的前提下，选择一些物品装入背包，使得装入背包中物品的总价值最大，并且总体积不超过背包容量。每个物品只能选择装入或不装入，不能部分装入。

下面我将为你详细解释自顶向下（记忆化搜索）和自底向上（迭代填表）两种动态规划实现方法，并提供相应的Python代码。

0-1背包问题的两种动态规划解法

1. 自顶向下：记忆化搜索 (Memoization, Top-Down)

自顶向下的方法采用递归的方式，但通过记忆化（存储已计算子问题的解）来避免重复计算，本质是深度优先搜索的优化。

• 状态定义：dp(i, j) 表示考虑前 i 个物品（即物品索引 0 到 i-1），在剩余容量为 j 的背包中，所能获得的最大价值。
• 记忆化：使用一个字典（或二维数组）memo 来存储已经计算过的 (i, j) 组合的结果。
• 递归流程：
  1. 基准情况：当没有物品可选 (i == 0) 或背包已满 (j == 0) 时，最大价值为 0。
  2. 查找备忘录：如果当前状态 (i, j) 已计算过，直接返回存储的值。
  3. 决策与状态转移：
     • 如果当前物品重量 weights[i-1] 大于剩余容量 j，无法放入，则最大价值等于不考虑当前物品的情况：dfs(i-1, j)。
     • 否则，可以选择放入或不放入当前物品，取两者中的最大值：
       max(dfs(i-1, j), dfs(i-1, j - weights[i-1]) + values[i-1])
  4. 存储结果：将计算结果存入备忘录，再返回。

def knapsack_memo(values, weights, capacity):
    """
    自顶向下记忆化搜索解决0-1背包问题
    
    :param values: 物品价值列表
    :param weights: 物品重量列表
    :param capacity: 背包容量
    :return: 背包能装的最大价值
    """
    n = len(values)
    # 备忘录，键为(i, j)，值为考虑前i个物品、容量为j时的最大价值
    memo = {}
    
    def dfs(i, j):
        # 基准情况：无物品或容量为0
        if i == 0 or j == 0:
            return 0
        # 如果已计算，直接返回
        if (i, j) in memo:
            return memo[(i, j)]
        
        # 当前物品重量超过剩余容量，只能不选
        if weights[i-1] > j:
            res = dfs(i-1, j)
        else:
            # 选择当前物品：价值增加，容量减少
            take = dfs(i-1, j - weights[i-1]) + values[i-1]
            # 不选择当前物品：价值和容量不变
            skip = dfs(i-1, j)
            # 取两者最大值
            res = max(take, skip)
            
        # 记录当前状态的结果
        memo[(i, j)] = res
        return res
    
    return dfs(n, capacity)

# 示例使用
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print("自顶向下（记忆化搜索）最大价值:", knapsack_memo(values, weights, capacity))

2. 自底向上：迭代填表 (Tabulation, Bottom-Up)

自底向上的方法采用迭代的方式，从最小的子问题开始，逐步构建更大问题的解，通常使用DP表（二维数组）来记录所有状态的结果。

• 状态定义：dp[i][j] 表示考虑前 i 个物品（物品索引 0 到 i-1），在背包容量为 j 时，所能获得的最大价值。
• 初始化：
  • dp[0][j] = 0：考虑前0个物品，任何容量下的最大价值都是0。
  • dp[i][0] = 0：背包容量为0时，无法装入任何物品，最大价值为0。
• 状态转移方程：
  • 如果当前物品重量 weights[i-1] 大于当前背包容量 j，无法放入：
    dp[i][j] = dp[i-1][j]
  • 否则，在放入和不放入当前物品之间选择最大值：
    dp[i][j] = max(dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1])
• 填表顺序：外层循环遍历物品 i 从 1 到 n，内层循环遍历容量 j 从 1 到 capacity。

def knapsack_tabulation(values, weights, capacity):
    """
    自底向上迭代填表解决0-1背包问题
    
    :param values: 物品价值列表
    :param weights: 物品重量列表
    :param capacity: 背包容量
    :return: 背包能装的最大价值
    """
    n = len(values)
    # 初始化DP表，(n+1) x (capacity+1)，初始值均为0
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    # 构建DP表
    for i in range(1, n + 1): # 遍历物品
        for j in range(1, capacity + 1): # 遍历容量
            # 当前物品索引是i-1（因为dp表行索引i对应前i个物品）
            current_weight = weights[i-1]
            current_value = values[i-1]
            
            if current_weight > j:
                # 当前物品太重，放不下，继承不放该物品时的价值
                dp[i][j] = dp[i-1][j]
            else:
                # 决策：放入或不放入当前物品，取最大值
                # 放入：当前物品价值 + 剩余容量在前i-1个物品中的最大价值
                value_if_take = dp[i-1][j - current_weight] + current_value
                # 不放入：前i-1个物品在当前容量下的最大价值
                value_if_skip = dp[i-1][j]
                dp[i][j] = max(value_if_take, value_if_skip)
                
    return dp[n][capacity]

# 示例使用
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print("自底向上（迭代填表）最大价值:", knapsack_tabulation(values, weights, capacity))

3. 获取具体装入方案

通过反向追踪DP表，可以知道哪些物品被选中。

def knapsack_with_trace(values, weights, capacity):
    n = len(values)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    # 构建DP表
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i-1] > j:
                dp[i][j] = dp[i-1][j]
            else:
                take_value = dp[i-1][j - weights[i-1]] + values[i-1]
                skip_value = dp[i-1][j]
                dp[i][j] = max(take_value, skip_value)
    
    # 反向追踪找出被选中的物品
    selected_items = []
    i, j = n, capacity
    while i > 0 and j > 0:
        # 如果dp[i][j]不等于dp[i-1][j]，说明第i个物品（索引i-1）被选中了
        if dp[i][j] != dp[i-1][j]:
            selected_items.append(i-1) # 记录物品索引
            j -= weights[i-1] # 回溯背包容量
        i -= 1 # 继续检查前一个物品
    
    selected_items.reverse() # 因为我们是从后往前追溯的，所以反转一下列表
    total_value = dp[n][capacity]
    return total_value, selected_items

# 示例使用
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
max_value, selected = knapsack_with_trace(values, weights, capacity)
print("最大价值:", max_value)
print("选中的物品索引:", selected) # 输出可能是 [1, 2] (即重量20和30的物品)

4. 空间优化：一维DP数组

观察状态转移方程，dp[i][j] 只依赖于 dp[i-1][...]（上一行），因此可以将二维DP表优化为一维数组，逆序更新以避免覆盖需要使用的上一行数据。

def knapsack_optimized(values, weights, capacity):
    """
    使用一维数组进行空间优化的自底向上解法
    """
    n = len(values)
    # 初始化一维DP数组，dp[j]表示容量为j时的最大价值
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # 必须逆序遍历容量！避免重复选取物品（覆盖了还未使用的前i-1个物品状态）
        for j in range(capacity, weights[i] - 1, -1):
            # 对于当前物品i，容量j足够的情况下
            # 比较不选它（dp[j]）和选它（dp[j - weights[i]] + values[i]）的价值
            if j >= weights[i]:
                dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
                
    return dp[capacity]

# 示例使用
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print("空间优化（一维数组）最大价值:", knapsack_optimized(values, weights, capacity))

方法对比与总结

核心思想：两种方法都利用了动态规划的重叠子问题和最优子结构性质。记忆化搜索是“懒惰计算”，按需求解；迭代填表是“主动计算”，预先求解所有可能子问题。