Python 算法教程（16）：动态规划之背包问题详解

前言

背包问题是动态规划最经典的问题之一，在面试中出现频率极高。本文详细讲解 0-1 背包、完全背包、多重背包三种变体。

一、0-1 背包问题

问题描述

有 N 件物品和一个容量为 W 的背包。第 i 件物品的重量是 weight[i]，价值是 value[i]。每件物品只能用一次，求解将哪些物品装入背包里可使价值总和最大。

状态转移方程

dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

其中：
- dp[i][w] 表示前 i 个物品，容量为 w 时的最大价值
- 不选第 i 个物品：dp[i-1][w]
- 选第 i 个物品：dp[i-1][w-weight[i]] + value[i]

代码实现

def knapsack_01(weight, value, W):
    n = len(weight)
    # dp[i][w] 表示前 i 个物品，容量为 w 时的最大价值
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(W + 1):
            # 不选第 i 个物品
            dp[i][w] = dp[i-1][w]
            # 选第 i 个物品（如果能装下）
            if w >= weight[i-1]:
                dp[i][w] = max(dp[i][w], dp[i-1][w-weight[i-1]] + value[i-1])
    
    return dp[n][W]

# 测试
weight = [2, 3, 4, 5]
value = [3, 4, 5, 6]
W = 8
print(knapsack_01(weight, value, W))  # 输出：10

空间优化（滚动数组）

def knapsack_01_optimized(weight, value, W):
    n = len(weight)
    # 一维数组优化
    dp = [0] * (W + 1)
    
    for i in range(n):
        # 倒序遍历，避免重复使用
        for w in range(W, weight[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i])
    
    return dp[W]

二、完全背包问题

问题描述

每种物品有无限个，可以重复使用。

关键区别

# 正序遍历，允许重复使用
for i in range(n):
    for w in range(weight[i], W + 1):  # 正序
        dp[w] = max(dp[w], dp[w - weight[i]] + value[i])

代码实现

def knapsack_complete(weight, value, W):
    n = len(weight)
    dp = [0] * (W + 1)
    
    for i in range(n):
        for w in range(weight[i], W + 1):
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i])
    
    return dp[W]

三、多重背包问题

问题描述

每种物品有有限个，第 i 种物品有 count[i] 个。

解法 1：转化为 0-1 背包

def knapsack_multiple(weight, value, count, W):
    # 转化为 0-1 背包
    new_weight = []
    new_value = []
    
    for i in range(len(weight)):
        for j in range(count[i]):
            new_weight.append(weight[i])
            new_value.append(value[i])
    
    return knapsack_01_optimized(new_weight, new_value, W)

解法 2：二进制优化

def knapsack_multiple_binary(weight, value, count, W):
    new_weight = []
    new_value = []
    
    for i in range(len(weight)):
        c = count[i]
        k = 1
        # 二进制拆分
        while k <= c:
            new_weight.append(k * weight[i])
            new_value.append(k * value[i])
            c -= k
            k *= 2
        if c > 0:
            new_weight.append(c * weight[i])
            new_value.append(c * value[i])
    
    return knapsack_01_optimized(new_weight, new_value, W)

四、复杂度对比

五、LeetCode 实战

416. 分割等和子集

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for i in range(target, num - 1, -1):
            dp[i] = dp[i] or dp[i - num]
    
    return dp[target]

322. 零钱兑换（完全背包）

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

六、面试考点

1. 0-1 背包为什么倒序？ - 避免重复使用同一物品
2. 完全背包为什么正序？ - 允许重复使用
3. 如何初始化 dp 数组？ - 根据问题要求，求最大值初始化为 0，求最小值初始化为无穷大
4. 如何优化空间？ - 使用一维数组滚动更新

总结

背包问题是动态规划的基础，掌握三种变体的区别和联系，能够解决大部分 DP 问题。

下一篇：最长递增子序列

cnbugsai

打赏 海报 链接