动态规划 - 背包问题

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[…] = -\infin,\ f[0] = 0$ （负无穷代表不合法状态）

习题

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