背包问题 - dpeng's Blog

背包问题是动态规划问题中选或者不选的典型代表, 从 0x3f 博主视频中，可以学习到用记忆化搜索的方式思考dp问题，这样可以让我们在写递推的时候，比较容易地想到状态数组的定义。本文将依照记忆化搜索 -> dp数组 -> dp数组优化的方式一步步讲解背包问题。

1. 01背包问题#

问题描述：有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只有一个。第 $i$ 件物品的体积是 $v_i$ ，价值是 $w_i$ 。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

首先我们想怎么样写出一个暴力搜索，可以覆盖全部的情况然后记录最大价值呢？于是开始构造搜索函数，可以发现对于第 $i$ 件物品，我们要么选择它要么不选择它，选取这二者的最大值，根据这两种情况得到搜索的方向，可以得到搜索函数：

dfs(i, j) = \begin{cases} dfs(i-1,j) & \text{if } j < v[i] \\ \\ \max (dfs(i-1,j), dfs(i-1,j-v[i])+w[i]) & \text{if } j \ge[i] \end{cases}

$i$ 代表第 $i$ 个物品， $j$ 代表当前背包的体积， $dfs(i,j)$ 代表从前 $i$ 个物品中选，选出体积为 $j$ 的物品的最大价值。

可以知道搜索函数的代码：

1
public int dfs(int i, int j) {
2
    if(i < 0) {
3
        return 0;
4
    }
5
    int ans = dfs(i - 1, j);
6
    if(j >= v[i]) {
7
        ans = Math.max(ans, dfs(i - 1, j - v[i]) + w[i]);
8
    }
9
    return ans;
10
}

在搜索的过程中会有一些节点被重复的搜索，导致算法的时间性能下降，为了改进这一点，我们需要对搜索进行记忆化，对于 01背包 这个问题，我们可以开一个二维数组用来进行记忆化每一个计算过的节点，记忆化搜索的代码如下：

1
public int dfs(int i, int j) {
2
    if(i < 0) {
3
        return 0;
4
    }
5
    if(memo[i][j] != -1) {
6
        return memo[i][j];
7
    }
8
    int ans = dfs(i - 1, j);
9
    if(j >= v[i]) {
10
        ans = Math.max(ans, dfs(i - 1, j - v[i]) + w[i]);
11
    }
12
    return memo[i][j] = ans;
13
}

下面让我们把这个代码改成递推的，其实一旦搜索的代码写出来了，动态规划的状态转移方程就出来了。

设置 dp[i][j] 表示为从前 $i$ 个物品中选，选出体积为 $j$ 的物品的最大值，状态转移方程为：

dp[i][j] = \begin{cases} dp[i-1][j] & \text{if } j < v[i] \\ \\ \max (dp[i-1][j], dp[i-1][j-v[i]]+w[i]) & \text{if } j \ge[i] \end{cases}

可以得到递推的代码如下：

1
int[][] dp = new int[n + 1][volume + 1];
2

3
for(int i = 0; i < n; i ++) {
4
    for(int j = 0; j <= volume; j ++) {
5
        dp[i + 1][j] = dp[i][j];
6
        if(j >= v[i]) {
7
            dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j - v[i]] + w[i]);
8
        }
9
    }
10
}

这里我们对递推的代码分析一下，可以知道对于 dp[i + 1] 层的数据的更新只需要用到 dp[i] 层的数据，所以空间上还可以优化。利用滚动数组的思想，我们不需要二维数组，只需要一维就够了。

在每次更新的时候，我们只需要保证“用来更新的数据是上一层的数据”就可以了，可以发现如果改成一维数组之后仍然使用体积从小到大进行遍历的话，就会导致更新时用到了当前层刚更新的数据，导致更新错误，所以我们要按照体积从大到小进行遍历

可以得到优化空间后的代码如下：

1
int[] dp = new int[volume + 1];
2

3
for(int i = 0; i < n; i ++) {
4
    for(int j = volume; j >= v[i]; j --) {
5
        dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
6
    }
7
}

2. 完全背包问题#

问题描述：有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品有无穷多个。第 $i$ 件物品的体积是 $v_i$ ，价值是 $w_i$ 。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

和01背包一样，我们也可以想一个覆盖全部情况的一个暴力搜索

1. 01背包问题#

2. 完全背包问题#

3. 多重背包问题#

4. 分组背包问题#