动态规划 - 背包问题

1. 01 背包

描述

有 $N$ 件物品和一个容量为 $V$ 的背包。放入第 $i$ 件物品占用的体积是 $C_i$，得到的价值是 $W_i$。求解在不超过 $V$ 的容量限制下，将哪些物品装入背包可使价值总和最大。

状态定义

令 $f_{i, j}$ 表示将前 $i$ 件物品装入容量为 $j$ 的背包中，所获得的最大价值。

状态转移方程

$$
f_{i, j} = max(f_{i - 1, j}, \ f_{i - 1, j - C_i} + W_i)
$$

memset(f, 0, sizeof(f));
for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= V; j++) {
        if (j < C[i]) f[i][j] = f[i - 1][j];
        else f[i][j] = max(f[i - 1][j], f[i - 1][j - C[i]] + W[i]);
    }
}

空间优化

按照合理的枚举顺序，可以将物品这一维度“滚动”掉。

memset(f, 0, sizeof(f));
for (int i = 1; i <= N; i++) {
    for (int j = V; j >= C[i]; j--) {
        f[j] = max(f[j], f[j - C[i]] + W[i]);
        // 这里的 f[j] 就是二维 f 版本中的 f[i - 1][j]
        // 故可以不考虑 j < C[i] 时的情况（不变即继承）
    }
}

习题

[NOIP 2005 普及组] 采药：⭐️

2. 完全背包

描述

有 $N$ 种物品和一个容量为 $V$ 的背包，每种物品都有无限件。放入第 $i$ 种物品占用的体积是 $C_i$，得到的价值是 $W_i$。求解在不超过 $V$ 的容量限制下，将哪些物品装入背包可使价值总和最大。

状态定义

令 $f_{i, j}$ 表示将前 $i$ 件物品装入容量为 $j$ 的背包中，所获得的最大价值。

状态转移方程 1

$$
f_{i, j} = max(f_{i, j - k \cdot C_i} + k \cdot W_i \ | \ 0 \leq k \cdot C_i \leq V)
$$

时间复杂度：$O(N \cdot V \cdot \sum_ {i = 1} ^ {N}\frac{V}{C_i})$

状态转移方程 2

$$
f_{i, j} = max (f_{i - 1, j}, \ f_{i, j - C_i} + W_i)
$$

时间复杂度：$O(N \cdot V)$，相比于第一种滚动掉了一重循环，避免了显式枚举。

memset(f, 0, sizeof(f));
for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= V; j++) {
        if (j < C[i]) f[i][j] = f[i - 1][j];
        else f[i][j] = max(f[i - 1][j], f[i][j - C[i]] + W[i]);
    }
}

空间优化

按照合理的枚举顺序，可以将物品这一维度“滚动”掉。

memset(f, 0, sizeof(f));
for (int i = 1; i <= N; i++) {
    for (int j = C[i]; j <= V; j++) {
        f[j] = max(f[j], f[j - C[i]] + W[i]);
        // j 的循环顺序与 01 背包中的相反
        // 正序枚举能保证目前参考到的以前的最优解，是可能包含选 i 这种物品的
    }
}

注意

对于所有背包问题，问题描述中若要求恰好装满，则只需要改变对于状态的初始化（改变状态的初始化，就能改变状态的含义）。

$\leq V$：$f[…] = 0$

$= V$：$f[…] = -\inf,\ f[0] = 0$ （负无穷代表不合法状态）

习题

疯狂的采药：⭐️
[NOIP 2017 提高组] 货币系统：⭐️⭐️
[CSP-J 2019] 纪念品：⭐️⭐️⭐️

3. 多重背包

描述

有 $N$ 种物品和一个容量为 $V$ 的背包，每种物品有 $M_i$ 件可用。放入第 $i$ 种物品占用的体积是 $C_i$，得到的价值是 $W_i$。求解在不超过 $V$ 的容量限制下，将哪些物品装入背包可使价值总和最大。
（与完全背包很像，完全背包可以看作是每种物品有 $\left\lfloor \frac{V}{C_i} \right\rfloor$ 件可用）。

状态定义

令 $f_{i, j}$ 表示将前 $i$ 件物品装入容量为 $j$ 的背包中，所获得的最大价值。

状态转移方程 1

$$
f_{i, j} = max(f_{i - 1, j - k \cdot C_i} + k \cdot W_i \ | \ 0 \leq k \leq M_i)
$$

时间复杂度：$O(V \cdot \sum_ {i = 1} ^ {N} M_i)$

状态转移方程 2

在这里使用 $[c, w]$ 的方式表示一件体积为 $c$，价值为 $w$ 的物品。

将 $M_i$ 进行二进制拆分，将 $M_i$ 件 $[C_i, W_i]$ ，转化为：

$$
[C_i, W_i], [2 \cdot C_i, 2 \cdot W_i], [2 ^ 2 \cdot C_i, 2 ^ 2 \cdot W_i], \ \cdots, \ [2 ^ {k - 1} \cdot C_i, 2 ^ {k - 1} \cdot W_i], [(M_i - 2 ^ k + 1) \cdot C_i, (M_i - 2 ^ k + 1) \cdot W_i]
$$

其中 $k$ 是满足 $M_i - 2 ^ k + 1 > 0$ 的最大整数。

易证对这 $\log_2(M_i)$ 件新物品的选择与否，能够表示取 $[0, M_i]$ 件原物品的所有情况。

证明：
将拆分出来的新物品用其对应的系数表示。在这里将新物品分为常规物品（系数为 $2$ 的整数次幂的物品）和超级物品（系数为 $M_i - 2 ^ k + 1$ 的物品）。

根据二进制的表示原理，$1, 2, 2 ^ 2, \cdots, 2 ^ {k - 1}$ 的选与不选，可以表示 $[0, 2 ^ k - 1]$ 里的所有数字。现还需要表示 $[2 ^ k, M_i]$ 之间的数字。

又因为：
$$
1 + 2 + 2 ^ 2 + \cdots + 2 ^ {k - 1} = \frac{1 \cdot (1 - 2 ^ {k})}{1 - 2} = 2 ^ k - 1
$$