已知有 $n$ 种物品,物品 $i$ 的重量为 $w_i \ge 0$(Weight),价值 为 $v_i \ge 0$(Value)。现在我们有一个最大承重量为 $C$ 的背包(Capacity),现在要求用此背包带走尽量高价值的物品,应该如何选择,此问题被称为 背包问题。

0-1 背包

问题定义

如果限定每种物品只能选择 0 个或 1 个,则问题称为 0-1 背包问题。

如果用公式表达,可以表示为: $$ \begin{aligned} &\operatorname{maxmize} &\sum_{i=1}^n v_i x_i & \\ &\operatorname{subject to} &\sum_{i=1}^n w_i x_i & \le C, x_i \in \{0, 1\} \\ \end{aligned} $$

解题思路

首先回顾一下 动态规划 三部曲(见本博客):

  1. 想清楚应该保存什么;
  2. 找递推关系式;
  3. 找初始值。

在 0-1 背包问题中对应如下:

第一步找记忆。我们可以用一个二维数组 $M$ 来保存「记忆」,大小为 $(n + 1) \times (C + 1)$,上面的每一个元素 $M_{i,j}$ 表示只考虑前 $i$ 件物品时,一个容量为 $j$ 的背包所能够获得的最大价值。

第二步找递推关系式。对于 $M$ 中的一个元素 $M_{i, j}$,其递推关系式如下: $$ M_{i,j} = \max\{ M_{i - 1, j}, M_{i - 1, j - w_i} + v_i \} $$

其中,$M_{i - 1, j}$ 表示只考虑前 $i - 1$ 件物品时,一个容量为 $j$ 的背包所能够获得的最大价值;$M_{i - 1, j - w_i} + v_i$ 表示只考虑前 $i - 1$ 件物品时,一个容量为 $j - w_i$ 的背包能够获得的最大价值加上第 $i$ 件物品的价值。如果 $\max$ 的是前一项,那么表示我们不取第 $i$ 件物品进背包;否则表示我们将会取第 $i$ 件物品。这里要注意如果第 $i$ 件物品的种类超过背包容量 $C$,就直接取前者。

第三步找初始值。我们可以使得外层循环是考虑第 $1$ 到第 $n$ 个物品,内层循环则是背包容量从 $1$ 到 $C$。那么初始值就是只考虑第 $0$ 个物品时,背包容量从 $1$ 到 $C$ 的最大价值(初始化为 0),以及背包容量为 $0$ 时,考虑第 $1$ 到 $n$ 个物品的最大价值(初始化为 0)。

由此,我们获得了 0-1 背包问题 的动态规划解法: $$ M_{i,j} = \begin{cases} &0 & \text{if }i = 0 \\ &0 & \text{if }j = 0 \\ &M_{i - 1, j} & \text{if }w_i > j \\ &\max\{ M_{i - 1, j}, M_{i - 1, j - w_i} + v_i \} &\text{otherwise} \\ \end{cases} $$

代码实现

光说不练假把式,下面上代码。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def knapsack(c, w, v):
    """动态规划解 0-1 背包问题。
    Args:
        c (int): 背包最大容量。
        w (list): 每件物品的重量,长度为 n。
        v (list): 每件物品的价值,长度为 n。
    """
    n = len(w)
    w.insert(0, 0)
    v.insert(0, 0)

    m = [[0 for _ in range(c + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, c + 1):
            if w[i] > j:
                m[i][j] = m[i - 1][j]
            else:
                m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i])

    return m, max(m[-1])

m, _ = knapsack(c=10, w=[2, 2, 6, 5, 4], v=[6, 3, 5, 4, 6])
m
# [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
#  [0, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6],
#  [0, 0, 6, 6, 9, 9, 9, 9, 9, 9, 9],
#  [0, 0, 6, 6, 9, 9, 9, 9, 11, 11, 14],
#  [0, 0, 6, 6, 9, 9, 9, 10, 11, 13, 14],
#  [0, 0, 6, 6, 9, 9, 12, 12, 15, 15, 15]]

注意这里之所以使用 insert 操作,是因为矩阵 $M$ 多了 0 行、0 列作为初始值,为了方便变量 w、v 坐标对齐,所以多加了一个 0 进去。

优化

降低空间复杂度

在上面的例子中,为了方便演示,所以把整个 $M$ 都存下来了,实际上并 不需要全部存下来,只需要保存 2 行即可,每次计算新的一行时只需要上一行的记录即可,这样的话可以大大减少空间复杂度。

更进一步,其实我们不需要保存 2 行,只需要保存一行,只要 内循环从大到小即可,就不会出现覆盖的问题。

输出选择的物品

我们可以写一个物品类,把每个物品都建成一个对象,然后对应矩阵 $M$ 的每个元素都存一个 list 保存指向选择的物品的指针。

要求刚好装满

如果要求「背包刚好装满」,那么与前面的「背包可以不装满」相比,区别只在动态规划矩阵 $M$ 的初始化:

  • 原来的初始化是只要能放就放,不管是否有剩余空间,所以矩阵 $M$ 的第 0 行、第 0 列都初始化为 0,意思是剩余多少容量都是合法的。
  • 现在要求恰好装满,那么我们只能初始化 $M_{0,0}$ 为 0,第 0 行、第 0 列的其他值都初始化为 -INF(Python 中为 float('-inf')),表示剩余容量不为 0 的时候不合法。

其他步骤与算法保持不变。

无界背包(完全背包)

如果不限定每种物品的数量,则称为 无界背包问题。

与 0-1 背包问题 相比,在 无界背包问题 中,每件物品都可以取任意件,那么在实现思路上的区别则是在递推关系式中,我们不再是求两个值的 $\max$(不放当前物品、放当前物品),而是求多个值的 $\max$(放 $k$ 件当前物品,$k \in \{ 0, 1, \cdots, \lfloor \frac{j}{w_i}] \rfloor \}$): $$ M_{i,j} = \max\{ M_{i - 1, j - k \cdot w_i} + k \cdot v_i ~|~ k \in \{ 0, 1, \cdots, \lfloor \frac{j}{w_i}] \rfloor \} \} $$

在实现上,也是在递推的时候将原来的 max 处改成长度为 k+1 的循环即可。

有界背包

如果限定物品 $i$ 最多只能选择 $b_i$ 个,则称为 有界背包问题。

该问题相当于 无解背包问题 加多一个限制条件:$k \le b_i$,实现上改动很小。

实战例子

在 LeetCode 随便找了几道背包题:

  • 《LeetCode 416. 分割等和子集 ⌨️》(0-1 背包)
  • 《LeetCode 322. 零钱兑换 ⌨️》(无界背包)

参考

▲