动态规划：完全背包问题-二维数组和一维滚动数组解法_二维完全背包

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。

输入描述

第一行包含两个整数，N，V，分别表示研究材料的种类和行李空间

接下来包含 N 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值

输出描述

输出一个整数，表示最大价值。

输入示例

4 5
1 2
2 4
3 4
4 5

输出示例

10

提示信息

第一种材料选择五次，可以达到最大值。

数据范围：

1 <= N <= 10000;
1 <= V <= 10000;
1 <= wi, vi <= 10^9.

思路1：二维dp数组

经典的多重背包问题，定义一个二维的dp数组，行是物品的编号，从$0\sim M-1$，列是背包的容量，从$0\sim N$，所以我们定义的二维dp数组行数为$M$，列数为$N+1$。另外我定义了一个一维数组$weight$存放物品的质量，再定义一个一维数组$value$存放物品的价值，它们的维度都是$M$。

怎么初始化dp数组呢：

首先是数组的第一行，我们把行索引固定为$0$，列索引$j$从0递增到$N$，对应dp数组每一个元素是$dp[0][j]$，如果此时的$j<weight[0]$，意味着背包放不下第一个物品（前一项是背包的容量，后一项是第一个物品的质量），这时候$dp[0][j]$赋值为$0$，否则可以放下物品，赋值为$dp[0][i-weight[0]]+value[0]$，$dp[0][i-weight[0]]$是背包容量为$i-weight[0]$的最大价值（拿掉第一种物品的个数为1），这时候再加上第一种物品的价值，就是背包容量为$i$的最大价值。

接着是数组的第一列，列索引固定为$0$，表示背包的容量为$0$，这时候无论物品的质量是多少，都放不进背包，这一列的所有元素价值都为$0$。

剩余的元素行索引的范围从$1\sim M-1$，列索引从$1\sim N$，其dp数组的递推公式为：

$$dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+value[i])$$

这里可能出现数组越界的情况：$j-item[i][0]<0$
所以dp数组的递推公式我们改为（关于这个递推公式的详细推导，我推荐看这个视频，讲得很清楚：【超精细!】动态规划—完全背包问题全面解读！！）：

d p [ i ] [ j ] = { m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − w e i g h t [ i ] ] + v a l u e [ i ] ) i f j − w e i g h t [ i ] ≥ 0 d p [ i − 1 ] [ j ] i f j − w e i g h t [ i ] < 0 dp[i][j]=\left\{

$$\begin{aligned} &max(dp[i - 1][j], dp[i ][j - weight[i]] + value[i]) &if \quad j - weight[i]\ge 0\\ &dp[i - 1][j] & if \quad j - weight[i]\lt 0\end{aligned}$$ \right. dp[i][j]={​max(dp[i−1][j],dp[i][j−weight[i]]+value[i])dp[i−1][j]​ifj−weight[i]≥0ifj−weight[i]<0​

$dp[i-1][j]$表示不放入编号为$i$物品的最大价值（物品编号从$0\sim i-1$），而$dp[i][j-weight[i]]+value[i])$表示考虑编号为$0\sim i$种物品的情况下背包容量$j$的最大价值。这两者的分别在于是否放入了编号为$i$的物品。和0-1背包相比，这个递推式的不同在于：

0-1背包 d p [ i ] [ j ] = { m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w e i g h t [ i ] ] + v a l u e [ i ] ) i f j − w e i g h t [ i ] ≥ 0 d p [ i − 1 ] [ j ] i f j − w e i g h t [ i ] < 0 完全背包 d p [ i ] [ j ] = { m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − w e i g h t [ i ] ] + v a l u e [ i ] ) i f j − w e i g h t [ i ] ≥ 0 d p [ i − 1 ] [ j ] i f j − w e i g h t [ i ] < 0

$$\begin{aligned} \text{0-1背包}\quad dp[i][j]&=\left\{\begin{aligned} &max(dp[i - 1][j], dp[{\color{Red} i - 1} ][j - weight[i]] + value[i]) &if \quad j - weight[i]\ge 0\\ &dp[i - 1][j] & if \quad j - weight[i]\lt 0\end{aligned}$$ \right.\\ \text{完全背包}\quad dp[i][j]&=\left\{ $$\begin{aligned} &max(dp[i - 1][j], dp[{\color{Red} i} ][j - weight[i]] + value[i]) &if \quad j - weight[i]\ge 0\\ &dp[i - 1][j] & if \quad j - weight[i]\lt 0\end{aligned}$$ \right. \end{aligned} 0-1背包dp[i][j]完全背包dp[i][j]​={​max(dp[i−1][j],dp[i−1][j−weight[i]]+value[i])dp[i−1][j]​ifj−weight[i]≥0ifj−weight[i]<0​={​max(dp[i−1][j],dp[i][j−weight[i]]+value[i])dp[i−1][j]​ifj−weight[i]≥0ifj−weight[i]<0​​

我们看到这个递推公式中$dp[i][j](1<=i<M,1<=j<=N)$和它的原始初始值没有关系，我们可以初始化为任意值，为了方便起见我们先把这个dp数组全部赋值为0。然后赋值第一行就可以了。我们的初始化可以写作：

vector<vector<int>> dp(N, vector<int>(V + 1, 0));
for (int i = weight[0]; i <= V; ++i){
    dp[0][i] = dp[0][i - weight[0]] + value[0];
}
1
2
3
4

完整的二维数组代码版本1（先遍历物品再遍历背包）：

#include <vector>
#include <iostream>
using namespace std;
int main(){
    int N, V;
    cin >> N >> V;
    
    vector<int> value(N);
    vector<int> weight(N);
    
    for (int i = 0; i < N; ++i){
        cin >> weight[i] >> value[i];
    }

    vector<vector<int>> dp(N, vector<int>(V + 1, 0));
    for (int i = weight[0]; i <= V; ++i){
        dp[0][i] = dp[0][i - weight[0]] + value[0];
    }
    
    
    for (int i = 1; i < N; ++i){ //先遍历物品，行
        for (int j = 1; j <= V; ++j) //后遍历背包，列
        {
            if (j >= weight[i])
                dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    cout << dp[N-1][V];
    return 0;
}
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
30
31
32

我们也可以先遍历背包再遍历物品，完整的二维数组代码版本2：

#include <vector>
#include <iostream>
using namespace std;
int main(){
    int N, V;
    cin >> N >> V;
    
    vector<int> value(N);
    vector<int> weight(N);
    
    for (int i = 0; i < N; ++i){
        cin >> weight[i] >> value[i];
    }

    vector<vector<int>> dp(N, vector<int>(V + 1, 0));
    for (int i = weight[0]; i <= V; ++i){
        dp[0][i] = dp[0][i - weight[0]] + value[0];
    }
    
    
    for (int j = 1; j <= V; ++j){ //先遍历背包，列
        for (int i = 1; i < N; ++i) //后遍历物品，行
        {
            if (j >= weight[i])
                dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    cout << dp[N-1][V];
    return 0;
}
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
30
31
32

思路2：滚动一维dp数组

我们也可以使用滚动一维dp数组来解决这个问题。相当于把二维数组做了一个压缩，之前我们做0-1背包问题，我们需要先遍历物品，再遍历背包，并且物品是正序遍历，背包是逆序遍历，而在完全背包问题里因为我们是使用当前行的数据，所以我们需要使用正序遍历。我们的动态规划的递推公式和0-1背包的递推公式是一样的：

d p [ j ] = { m a x ( d p [ j ] , d p [ j − w e i g h t [ i ] ] + v a l u e [ i ] ) i f j − w e i g h t [ i ] ≥ 0 d p [ j ] i f j − w e i g h t [ i ] < 0 dp[j] = \left\{

$$\begin{aligned} &max(dp[j], dp[j - weight[i]] + value[i]) &if \quad j - weight[i]\ge 0\\ &dp[j] & if \quad j - weight[i]\lt 0\end{aligned}$$ \right. dp[j]={​max(dp[j],dp[j−weight[i]]+value[i])dp[j]​ifj−weight[i]≥0ifj−weight[i]<0​

这里的i还是代表物品的编号，j代表背包的容量。

为什么要使用正序遍历背包呢？虽然是一维数组，但是性质和二维背包差不多。从每一个元素往前看，因为是正序遍历，所以前面的元素都被更新过了，看到的都是“上一层的元素”，正序遍历的前提下前面的元素都发生了改变，相当于是二维dp数组当前层的元素，元素使用了多次，符合完全背包的要求。

因为二维数组是根据左测（0-1背包是左上角）元素来求的，而一维数组自然就是靠左侧来求的。正序的时候，左边的元素刚刚刷新过，也就是左边的元素已经是本层的了，意味着什么这样会导致一个物品反复加好几次。和0-1背包不同，完全背包遍历的顺序是可以改变的。

初始化很简单，和0-1背包一样，因为我们要放置把我们的结果忽略掉（可能取$dp[j-weight[i]]+value[i]$）我们把一维数组全部初始化为0就可以了。

这里给出代码：

完整的一维滚动数组代码版本1（先遍历物品再遍历背包）

#include <vector>
#include <iostream>
using namespace std;
int main(){
    int N, V;
    cin >> N >> V;
    
    vector<int> value(N);
    vector<int> weight(N);
    
    for (int i = 0; i < N; ++i){
        cin >> weight[i] >> value[i];
    }
    
    vector<int> dp(V + 1, 0);
    
    for (int i = 0; i < N; ++i){ //先遍历物品，行
        for (int j = weight[i]; j <= V; ++j){ //再遍历背包，列
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        } 
    }

    cout << dp[V];
    return 0;
}
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

完整的一维滚动数组代码版本2（先遍历背包再遍历物品）：

```cpp
#include <vector>
#include <iostream>
using namespace std;
int main(){
    int N, V;
    cin >> N >> V;
    
    vector<int> value(N);
    vector<int> weight(N);
    
    for (int i = 0; i < N; ++i){
        cin >> weight[i] >> value[i];
    }
    
    vector<int> dp(V + 1, 0);
   
    for (int j = 0; j <= V; ++j){ //先遍历背包，列
        for (int i = 0; i < N; ++i){ //再遍历物品，行
            if (j >= weight[i])
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            else
                dp[j] = dp[j];
        }
    }

    cout << dp[V];
    return 0;
}
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

1