算法-背包问题

前言

背包问题是动态规划中的经典问题，也是算法面试中的高频考点。今天我们来深入探讨两种最基础也最重要的背包问题：0-1背包问题和完全背包问题。

什么是背包问题？

背包问题的基本场景是这样的：你有一个容量为 W 的背包，面前有 n 件物品，每件物品都有自己的重量 w[i] 和价值 v[i]。你需要选择哪些物品放入背包，使得在不超过背包容量的前提下，背包中物品的总价值最大。

这个问题在现实生活中有很多应用场景：

资源分配问题
投资组合优化
货物装载问题
任务调度问题

0-1背包问题

问题定义

0-1背包问题是最经典的背包问题。其特点是：每件物品最多只能选择一次，要么选（1），要么不选（0），这就是”0-1”名称的由来。

问题描述：
给定 n 件物品，第 i 件物品的重量为 w[i]，价值为 v[i]。现有一个容量为 W 的背包，求在不超过背包容量的情况下，能够装入背包中的物品的最大价值。

动态规划思路

我们用 dp[i][j] 表示前i件物品放入容量为j的背包中能够获得的最大价值。

状态转移方程：

1	dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

这个方程的含义是：

dp[i-1][j]：不选择第 i 件物品的最大价值
dp[i-1][j-w[i]] + v[i]：选择第 i 件物品的最大价值（前提是 j >= w[i]）

边界条件：

dp[0][j] = 0：没有物品时，价值为0
dp[i][0] = 0：背包容量为0时，价值为0

代码实现

def knapsack_01(weights, values, capacity):
    n = len(weights)
    # dp[i][j]表示前i件物品放入容量为j的背包的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            # 不选择第i件物品
            dp[i][j] = dp[i-1][j]
            
            # 如果能放下第i件物品，考虑选择它
            if j >= weights[i-1]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-weights[i-1]] + values[i-1])
    
    return dp[n][capacity]

# 示例
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(f"0-1背包最大价值: {knapsack_01(weights, values, capacity)}")

空间优化

由于每次状态转移只依赖于上一行的数据，我们可以使用一维数组来优化空间复杂度：

def knapsack_01_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # 从右到左遍历，避免重复使用
        for j in range(capacity, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    
    return dp[capacity]

注意： 这里必须从右到左遍历，因为我们要保证每个物品只被使用一次。

完全背包问题

问题定义

完全背包问题与0-1背包问题的区别在于：每件物品可以无限次选择。

问题描述：
给定 n 种物品，每种物品的重量为 w[i]，价值为 v[i]，每种物品都有无限个。现有一个容量为 W 的背包，求在不超过背包容量的情况下，能够装入背包中的物品的最大价值。

动态规划思路

同样用 dp[i][j] 表示前i种物品放入容量为j的背包中能够获得的最大价值。

状态转移方程：

1	dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])

注意这里与0-1背包的区别：选择第 i 种物品时，状态从 dp[i][j-w[i]] 转移而来，而不是 dp[i-1][j-w[i]]，这意味着第i种物品可以重复选择。

代码实现

def knapsack_complete(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            # 不选择第i种物品
            dp[i][j] = dp[i-1][j]
            
            # 如果能放下第i种物品，考虑选择它
            if j >= weights[i-1]:
                dp[i][j] = max(dp[i][j], dp[i][j-weights[i-1]] + values[i-1])
    
    return dp[n][capacity]

# 示例
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(f"完全背包最大价值: {knapsack_complete(weights, values, capacity)}")

空间优化

完全背包的空间优化更加简单，因为可以重复选择，所以从左到右遍历即可：

def knapsack_complete_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # 从左到右遍历，允许重复使用
        for j in range(weights[i], capacity + 1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    
    return dp[capacity]

两种背包问题的对比

特征	0-1背包	完全背包
物品使用次数	每件物品最多用一次	每种物品可无限使用
状态转移	`dp[i-1][j-w[i]] + v[i]`	`dp[i][j-w[i]] + v[i]`
空间优化遍历方向	从右到左	从左到右
时间复杂度	`O(nW)`	`O(nW)`
空间复杂度	`O(W)` (优化后)	`O(W)` (优化后)

实际应用示例

让我们通过一个具体例子来感受两种背包问题的区别：

场景： 小明有 7 元钱，想买零食获得最大满足度。

商店里有以下零食：

薯片：3 元，满足度 4
巧克力：4 元，满足度 5
饮料：5 元，满足度 7
糖果：1 元，满足度 1

0-1背包（每种零食只能买一份）：
最优解：巧克力(4元) + 薯片(3元) = 7元，总满足度 = 9

完全背包（每种零食可以买多份）：
最优解：饮料(5元) + 糖果(1元) + 糖果(1元) = 7元，总满足度 = 9
或者：薯片(3元) + 薯片(3元) + 糖果(1元) = 7元，总满足度 = 9

后记

背包问题是动态规划的经典应用，掌握0-1背包和完全背包是学习更复杂背包问题的基础。

核心要点：

状态定义：dp[i][j] 表示前 i 个物品放入容量为 j 的背包的最大价值
状态转移：根据是否选择当前物品来决定状态转移方程
遍历顺序：0-1背包从右到左，完全背包从左到右
空间优化：都可以优化到 O(W) 的空间复杂度

理解了这两种基础的背包问题，你就能轻松应对多重背包、混合背包等更复杂的变种问题了。在实际编程中，背包问题的思想也经常被用来解决资源分配和优化问题。