【背包问题】三种背包问题（python实现）

甄心爱学习

863人浏览 · 2026-03-01 15:06:46

甄心爱学习 · 2026-03-01 15:06:46 发布

1. 0/1 背包

定义： 每种物品仅有一件，可以选择放（1）或不放（0）。

状态定义： dp[i][j] 表示在前 i 个物品中选择，且当前背包剩余容量为 j 时所能获得的最大价值。
状态转移方程：

$dp[i][j] = \max(dp[i-1][j], \quad dp[i-1][j-w[i]] + v[i])$
- dp[i-1][j]：不选第 i 个物品。
- dp[i-1][j-w[i]] + v[i]：选择第 i 个物品（前提是 $j \ge w[i]$ ）。
空间优化（滚动数组）：

由于 dp[i] 仅依赖于 dp[i-1]，可以优化为一维数组 dp[j]。

注意： 必须从 W 到 w[i] 逆序遍历。这是为了保证在计算 dp[j] 时，引用的 dp[j-w[i]] 仍然是“上一层（即 i-1）”的数据，防止物品被重复计算。

#一维数组实现
for j in range(W, w[i]-1, -1):
    dp[j] = max(dp[j], dp[j-w[i]] + v[i])

如果是二维数组，遍历正序列或是逆序都行，通常用正序

def knapsack_01_2d(W, weights, values):
    n = len(weights)
    # 初始化 (n+1) x (W+1) 的二维数组，全为 0
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        w = weights[i - 1]
        v = values[i - 1]
        
        for j in range(W + 1):  # 容量正序逆序皆可
            if j < w:
                # 容量不够，只能继承上一层的不选状态
                dp[i][j] = dp[i - 1][j]
            else:
                # 容量足够，决策：不选 vs 选
                # 注意：选用物品时，依赖上一层 dp[i-1]
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
                
    return dp[n][W]

2. 完全背包

定义： 每种物品有无限多件。

寻找的最优基础是 “可能已经包含了第 i 个物品的最优解”（即当前第 i 层）

状态转移方程：

虽然可以写成 $dp[i][j] = \max_{k=0}^{\infty}(dp[i-1][j - k \cdot w[i]] + k \cdot v[i])$ ，但更高效的表达是： $dp[i][j] = \max(dp[i-1][j], \quad dp[i][j-w[i]] + v[i])$
注意这里加号左边是 dp[i] 而不是 dp[i-1]，表示在选择了第 i 个物品后，依然可以继续选择第 i 个物品。
空间优化：

一维数组 dp[j] 必须顺序遍历。因为我们需要利用当前行已经更新过的值（即包含了可能已经选过该物品的状态）。

#一维数组实现
for j in range(w[i], W + 1):
    dp[j] = max(dp[j], dp[j-w[i]] + v[i])

如果是二维数组，遍历正序列或是逆序都行，通常用正序

def knapsack_complete_2d(W, weights, values):
    n = len(weights)
    # 初始化 (n+1) x (W+1) 的二维数组，全为 0
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        w = weights[i - 1]
        v = values[i - 1]
        
        for j in range(W + 1):  # 容量正序逆序皆可
            if j < w:
                dp[i][j] = dp[i - 1][j]
            else:
                # 注意唯一区别：选用物品时，依赖当前层 dp[i]
                dp[i][j] = max(dp[i - 1][j], dp[i][j - w] + v)
                
    return dp[n][W]

01背包与完全背包的代码实现对比（一维）：

代码在j的循环时，隐式的表明了目前的容量，如果容量不够，循环不会进入

# W: 背包总容量, n: 物品数量
# weights: 物品重量列表, values: 物品价值列表

def knapsack_01(W, n, weights, values):
    dp = [0] * (W + 1)
    for i in range(n):
        # 0/1 背包：必须逆序遍历容量，防止重复选择同一件物品
        for j in range(W, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[W]

def knapsack_complete(W, n, weights, values):
    dp = [0] * (W + 1)
    for i in range(n):
        # 完全背包：必须顺序遍历容量，允许重复选择同一件物品
        for j in range(weights[i], W + 1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[W]

3. 多重背包

思考

最简单的办法： 如果物品 i 有 s[i] 个，我直接把它看作 s[i] 个独立的、完全一样的 0/1 背包物品，逻辑上行得通吗？它的时间复杂度瓶颈在哪里？

数字组合： 给你数字 1, 2, 4，你能通过组合（加法）凑出 1 到 7 之间的任何整数吗？如果能，这对减少物品数量有什么启发？

滑动窗口： 在完全背包中，我们利用了“当前行”的连续性。在多重背包中，如果容量 j 和 j-w[i] 之间隔了超过 s[i] 个物品，我们还能直接引用吗？

多重背包的定义是：每种物品 i 最多有 s[i] 。

（1）暴力拆分

将 s[i]个相同的物品拆解为 s[i] 个独立的 0/1 物品。

状态转移：

$dp[j] = \max_{0 \le k \le s[i]} (dp[j - k \cdot w[i]] + k \cdot v[i])$
复杂度： $O(W \cdot \sum s[i])$
评价： 思路最简单，但在 s[i] 很大（如几万）时会超时（TLE）

def knapsack_bounded_naive(W, weights, values, counts):
    n = len(weights)
    dp = [0] * (W + 1)
    
    for i in range(n):
        w = weights[i]
        v = values[i]
        s = counts[i]
        
        # 必须像 0/1 背包一样【逆序】遍历容量
        for j in range(W, w - 1, -1):
            # 第三层循环：枚举当前物品 i 选择的件数 k
            # k 从 1 开始，最大到 s，且必须保证当前容量 j 足够放下 k 件
            for k in range(1, s + 1):
                if j >= k * w:
                    dp[j] = max(dp[j], dp[j - k * w] + k * v)
                else:
                    # 容量不足以放下更多的 k 件，直接剪枝跳出
                    break
                    
    return dp[W]

（2）二进制拆分优化

这是最常用、性价比最高的优化方式。其核心思想是：利用 $1, 2, 4, 8, \dots, 2^k$ 可以组合出 $0 \sim 2^{k+1}-1$ 之间的任何整数。

操作步骤：

对于数量为 s[i] 的物品，我们不把它拆成 $1, 1, 1, \dots$ （拆了 s[i] 次），而是拆成：

$1, 2, 4, \dots, 2^k$ 以及一个余数

例子： 如果某物品有 13 件。
- 拆分为：1, 2, 4 件。此时能凑出 $1 \sim 7$ 件。
- 剩下的件数：13 - 7 = 6 件。
- 最终包裹：这 13 件物品被打包成了四个“大商品”，数量分别为 1, 2, 4, 6。他们能组合出来1-13的所有数
- 结果： 原本要做 1 次决策，现在只需对这 4 个包裹做 0/1 背包决策。
复杂度： $O(W \cdot \sum \log s[i])$ 。
评价： 极大地降低了计算量，能应付绝大多数竞赛和面试题。

def knapsack_bounded_binary(W, n, weights, values, counts):
    # 新的物品列表，存储拆分后的重量和价值
    new_weights = []
    new_values = []
    
    for i in range(n):
        s = counts[i]
        w = weights[i]
        v = values[i]
        
        # 二进制拆分核心逻辑
        k = 1
        while k <= s:
            new_weights.append(k * w)
            new_values.append(k * v)
            s -= k
            k *= 2  # 1, 2, 4, 8...
            
        # 处理剩余的部分 (R)
        if s > 0:
            new_weights.append(s * w)
            new_values.append(s * v)
            
    # 转化后的问题变成了一个纯粹的 0/1 背包问题
    return knapsack_01(W, len(new_weights), new_weights, new_values)

（3）单调队列优化

这是多重背包的最优解法，可以将复杂度优化到与 0/1 背包同一量级。

核心逻辑：

观察状态转移：dp[j] 取决于 $dp[j-w[i]], dp[j-2w[i]], \dots, dp[j-s[i] \cdot w[i]]$

这些下标都有一个共同点：它们对 w[i] 取模的余数相同。

思路：

我们可以按照 $j \pmod{w[i]}$ 的余数 r 将 dp 数组分成 w[i] 组

对于每一组，这就变成了一个滑动窗口最值问题：在长度为 s[i] 的窗口内，找价值最大的那个状态
复杂度： $O(N \cdot W)$
评价： 实现较复杂，但在数据量极大的极端情况下（如 $W$ 很大且 $s[i]$ 很大）是唯一的生存手段。

from collections import deque

def knapsack_bounded_monotonic_queue(W, n, weights, values, counts):
    dp = [0] * (W + 1)
    
    for i in range(n):
        w, v, s = weights[i], values[i], counts[i]
        new_dp = dp[:] # 拷贝上一层状态
        
        # 按余数分组
        for r in range(w):
            queue = deque() # 存储下标，维护单调递减的价值
            for j in range(r, W + 1, w):
                # 1. 维护滑动窗口：计算当前状态与队列中旧状态的价值差
                # 这里的价值需要减去对应数量的 v，以便在统一基准下比较
                val = dp[j] - (j // w) * v
                
                # 保持队列单调递减
                while queue and queue[-1][1] <= val:
                    queue.pop()
                queue.append((j, val))
                
                # 2. 移除超出数量限制 s 的过期状态
                if queue[0][0] < j - s * w:
                    queue.popleft()
                
                # 3. 更新当前 dp 状态
                new_dp[j] = queue[0][1] + (j // w) * v
        dp = new_dp
    return dp[W]

方法	核心思想	时间复杂度	适用场景
暴力法	直接展开	$O(W \cdot \sum s)$	s 很小
二进制拆分	组合数学优化	$O(W \cdot \sum \log s)$	主流解法，大部分场景
单调队列	滑动窗口最值	$O(N \cdot W)$	追求极致性能