算法——动态规划：0/1 背包问题

一、问题描述

问题的抽象：给定 $n$ 种物品和一个背包，第 $i$ 个物品的体积为 $c_i$，价值为 $w_i$，背包的总容量为 $C$。把物品装入背包时，第 $i$ 种物品只有两种选择：装入背包或不装入背包。如何选择装入背包的物品，使装入背包中的物品的总价值最大？

具体的问题可以看这道洛谷题：P1048 [NOIP2005 普及组] 采药，将 物品 换成了 草药，将 容量 换成了 时间，将 背包的容量 换成了 规定的时间。

二、解决方案

0/1 背包问题 是一道 经典 的使用 动态规划 思想的题目，同时也不是很难，掌握它之后就正式跨入 动态规划 的大门了。

1. DP 状态的设计

引入一个 $(N+1)\times (C+1)$ 的二维数组 $dp[][]$，称为 DP 状态。其中，$dp[i][j]$ 表示把前 $i$ 个（从第 $1$ 个到第 $i$ 个）物品装入容量为 $j$ 的背包中获得的最大价值。

每个 $dp[i][j]$ 都是一个 0/1 背包问题：将前 $i$ 个物品装入容量为 $j$ 的背包。所以 $dp[N][C]$ 就代表将前 $N$ 个物品装入容量为 $C$ 的背包。

2. 状态转移方程

状态转移方程指的是 从一个状态转变到另一个状态的递推公式。

一般使用 自底向上 的 递推 来解决背包问题，假设已经递推到 $dp[i][j]$，分两种情况：

• 第 $i$ 个物品的体积比容量 $j$ 还大，不能装进容量为 $j$ 的背包。此时直接继承前 $i-1$ 个物品装进容量 $j$ 的背包的情况即可，即 $dp[i][j]=dp[i-1][j]$。
• 第 $i$ 个物品的体积比容量 $j$ 小，能装进背包。此时就体现 0/1 了（$0$ 表示不装，$1$ 表示装）：
  • 装第 $i$ 个物品。先在 前 $i-1$ 个物品装进容量为 $j$ 的背包中，给第 $i$ 个物品空出 $c_i$ 的空间，从而得到背包 $dp[i-1][j-c[i]]$。然后将第 $i$ 个物品放入这个背包，背包的价值增加 $w_i$，从而有当前背包 $dp[i][j]=dp[i-1][j-c[i]]+w[i]$。
  • 不装第 $i$ 个物品。直接继承前 $i-1$ 个物品装进容量 $j$ 的背包的情况即可，即 $dp[i][j]=dp[i-1][j]$。
  • 此时取这两者中的较大值作为当前背包的价值，状态转移方程为：$$dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])$$

所以 0/1 背包问题 的特征如下：

• 重叠子问题是 $dp[i][j]$
• 最优子结构是 $dp[i][j]$ 的状态转移方程。

3. 算法复杂度

• 时间复杂度：在计算时，需要计算二维矩阵 $dp[][]$ 中的每一个值，矩阵的大小是 $NC$，每次计算的时间为 $O(1)$，所以时间复杂度为 $O(NC)$。
• 空间复杂度：使用了大小为 $NC$ 的二维数组，所以空间复杂度为 $O(NC)$。

说明：如果 $N,C$ 很大，则 $N+1,C+1$ 可以近似地看作 $N,C$，为了简化，所以复杂度不是 $O((N+1)\times (C+1))$。

4. 举例

初学者可能很难理解，这时举一个实际案例就懂了。对于 P1048 题，有一个测试用例：背包的容量为 70，物品的数量为 3，物品的体积数组为 [71, 69, 1]，物品的价值数组为 [100, 1, 2]。

定义一个 4 * 71 的二维数组，如下所示（由于长度限制，中间的数全部用 ... 代替，... 代表的数 和 ... 两边的数相同）：

先填充索引为 1 的行（第一个物品的体积为 71，价值为 100）：

然后填充索引为 2 的行（第二个物品的体积为 69，价值为 1）：

接着填充索引为 3 的行（第三个物品的体积为 1，价值为 2）：

最终，数组的 dp[3][70] 的位置存储着题目的结果——将前 3 个物品放入容量为 70 的背包的最大价值。

5. 实现

// 虽然这些代码看起来是 C 语言的代码，但如果选择 C 语言，则会编译失败。建议选择 C++14
#include <stdio.h>const int MAX_N = 105; // 最大的物品数量，与题目有关
const int MAX_C = 1005; // 最大的背包容量，与题目有关
int N, C; // N 是物品的数量，C 是背包的容量
int c[MAX_N], w[MAX_N]; // c[i], w[i] 分别表示第 i 个物品的 体积 和 价值
int dp[MAX_N][MAX_C]; // dp[i][j] 表示将前 i 个物品装入容量为 j 的背包中// 取 x 和 y 中的较大值
int max(int x, int y) {return x > y ? x : y;
}// 进行动态规划
int programming() {for (int i = 1; i <= N; i++) {for (int j = 1; j <= C; j++) {if (j < c[i]) { // 装不下第 i 个物品dp[i][j] = dp[i - 1][j];} else { // 能装下第 i 个物品dp[i][j] = max(dp[i - 1][j - c[i]] + w[i], // 装第 i 个物品dp[i - 1][j] // 不装第 i 个物品);}}}return dp[N][C];
}int main() {// 读取数据scanf("%d %d", &C, &N);for (int i = 1; i <= N; i++) {scanf("%d %d", &c[i], &w[i]);}// 进行动态规划printf("%d", programming());return 0;
}

6. 滚动数组

滚动数组 是 动态规划 最常用的 空间优化技术。动态规划的状态方程通常是二维即以上，占用了太多空间，用滚动数组可以 极大程度上 减少空间占用，它能把 二维 状态方程的空间复杂度优化到 一维，更高维的数组也可以通过优化，减少一个维度。

从状态转移方程 $dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])$ 中可以看出，$dp[i][]$ 只与 $dp[i-1][]$ 有关，与之前的 $dp[i-2][],dp[i-3][],\cdots$ 都无关。由于它们都没用了，索性就 复用 它们占用的空间，用新的一行覆盖已经无用的一行，只需要两行就够了。这就是“滚动”的含义。

滚动数组根据使用的行数不同，分为两种实现方式：

6.1 两行实现

仍然使用二维数组，不过不是 $(N+1)\times (C+1)$ 的二维数组，而是 $2\times (C+1)$ 的二维数组，这就是所谓的“两行”：计算 本行 时用 上一行 的结果，然后将 本行 和 上一行 互换，计算 新的本行（新的本行 使用了 原来上一行 的内存空间）时使用 新的上一行（新的上一行 使用了 原来本行 的内存空间）。

#include <stdio.h>const int MAX_N = 105; // 最大的物品数量，与题目有关
const int MAX_C = 1005; // 最大的背包容量，与题目有关
int N, C; // N 是物品的数量，C 是背包的容量
int c[MAX_N], w[MAX_N]; // c[i], w[i] 分别表示第 i 个物品的 体积 和 价值
int dp[2][MAX_C]; // 使用两行滚动数组，dp[i][j] 成为不断更新的变量，没有固定的含义// 取 x 和 y 中的较大值
int max(int x, int y) {return x > y ? x : y;
}// 交换 i 和 j 的值
// 注意 &，它表示引用传递，使用传入的实参，而不是重新创建一个新变量来代表实参，这是 C++ 的特性
void swap(int &i, int &j) {int temp = i;i = j;j = temp;
}// 进行动态规划
int programming() {/*在状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]) 中，位于 dp 的行索引的 i 用 curr 来代替，i - 1 用 prev 来代替prev, curr 分别是 上一行 和 本行 索引*/int prev = 0, curr = 1;for (int i = 1; i <= N; i++) {swap(prev, curr); // 将本行和上一行互换for (int j = 1; j <= C; j++) {if (j < c[i]) { // 装不下第 i 个物品dp[curr][j] = dp[prev][j];} else { // 能装下第 i 个物品dp[curr][j] = max(dp[prev][j - c[i]] + w[i], // 装第 i 个物品dp[prev][j] // 不装第 i 个物品);}}}return dp[curr][C]; // 返回当前行的最后一个值
}int main() {// 读取数据scanf("%d %d", &C, &N);for (int i = 1; i <= N; i++) {scanf("%d %d", &c[i], &w[i]);}// 进行动态规划printf("%d", programming());return 0;
}

6.2 单行实现

实际上还能省，发现计算 $dp[i][j]$ 时会用到 $dp[i-1][j-c[i]]$ 和 $dp[i-1][j]$，所以还可以复用 上一行 中的部分内存空间。

由于 $j-c[i]$ 不是一个确定的值，取值范围为 $[0,j)$，所以 无法 在计算出 $dp[i][j]$ 的结果前 复用 上一行 中 $j$ 之前的内存空间。既然如此，就考虑 复用 上一行 中 $j$ 之后的内存空间。此时能想到：如果 从后向前计算 $dp[i][j]$，就不会影响 $j$ 之前的值。进而就有 单行 的滚动数组实现：

#include <stdio.h>const int MAX_N = 105; // 最大的物品数量，与题目有关
const int MAX_C = 1005; // 最大的背包容量，与题目有关
int N, C; // N 是物品的数量，C 是背包的容量
int c[MAX_N], w[MAX_N]; // c[i], w[i] 分别表示第 i 个物品的 体积 和 价值
int dp[MAX_C]; // 使用单行滚动数组，dp[j] 成为不断更新的变量，没有固定的含义// 取 x 和 y 中的较大值
int max(int x, int y) {return x > y ? x : y;
}// 进行动态规划
int programming() {for (int i = 1; i <= N; i++) {for (int j = C; j >= 1; j--) { // 切记要从后往前计算if (j < c[i]) { // 装不下第 i 个物品dp[j] = dp[j];} else { // 能装下第 i 个物品dp[j] = max(dp[j - c[i]] + w[i], // 装第 i 个物品dp[j] // 不装第 i 个物品);}}}return dp[C]; // 返回单行的最后一个值
}int main() {// 读取数据scanf("%d %d", &C, &N);for (int i = 1; i <= N; i++) {scanf("%d %d", &c[i], &w[i]);}// 进行动态规划printf("%d", programming());return 0;
}

6.3 优缺点

• 优点：优化了空间复杂度，很大程度上减少了内存的使用。
• 缺点：
  • 由于复用了空间，从而覆盖了之前的计算结果，数组中的值没有固定的实际含义，难以理解，通常都是先写出常规的动态规划，再使用滚动数组进行优化。
  • 还是因为复用了空间，导致只留下最后一次计算的状态，无法从数组中看出具体的方案。

三、总结

0/1 背包问题 的 0/1 在于每种物品只有两种状态——放进背包 和 不放进背包，针对这一问题，使用了 动态规划 的解决方案，由于空间复杂度比较高，所以还使用 滚动数组 的思想进行优化，从而将占用的空间 降维。初学者适合用 两行 的实现，不容易犯错。熟练掌握动态规划后，可以使用 单行 的实现。