VIRTUALS

the virtual labs for the virtuals

0%

【AcWing算法基础】第五讲-动态规划-背包问题 AcWing 2. 01背包问题

Posted on Edited on In , , , ,

摘要：
01背包模板题，非常纯粹。

题目

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i,w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

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

数据范围
$0 < N,V ≤ 1000$
$0 < v_i,w_i ≤ 1000$

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

设 i 为前 i 件物品，j 为背包的最大容量。
设 v[i] 为第 i 件物品的体积，w[i] 为第 i 件物品的价值。

二维dp数组

题目要求前 $N$ 个物品，放入容量为 $V$ 的背包中，所得到的最大价值。
由此可以定义一个二维dp数组 f[i][j] 用以表示状态。

状态集合： 前 i 个物品放入容量为 j 的背包中的所有情况所构成的集合。
其中 $1 <= i <= N, 1 <= j <= V$，即：
对于前 $1$ 件到前 $N$ 件中的每种情况，都分别对应背包容量从 $1$ 到 $V$ 的每种情况。所有情况构成了状态集合。

状态集合元素属性： 对于集合中的每个元素，将产生的最大价值定义为它的属性放在二维dp数组中。即：
f[i][j] 表示前 i 个物品放入容量为 j 的背包中，所对应的最大价值。

状态计算： 现在思考如何计算 f[i][j] 的值。
对于前 i 件物品的第 i 件物品，只会有 「可放入」背包和「不可放入」背包两种情况。现在考虑哪些情况可放入哪些不可放入。

  • 不可放入第 i 件物品：很容易想到，当尝试放入第 i 件物品时，遇到背包容量限制的时候，必然不可放入。即：
    当第 i 件的体积超出背包总体积时，必然不可放入（j < v[i]）。
    那么， f[i][j] 表示前 i - 1 件物品放入容量为 j 的背包中的最大价值。
  • 可放入第 i 件物品：反之， j >= v[i] ，即 j - v[i] >= 0 ，供前 i - 1 件物品放入的背包容量是大于零的。同时，注意，第 i 件可放可不放，没有条件限制。
    那么， f[i][j] 表示前 i - 1 件物品放入容量为 j - v[i] 的背包中的最大价值和
    第 i 件物品放入容量为 j 的背包中的最大价值，二者取较大者。

状态转移方程： 根据上述状态计算方式，可以得出状态转移方程分别为：

  • f[i][j] = f[i - 1][j]
  • f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])

其中 v[i] 和 w[i] 分别为第 i件物品的体积和价值。

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
33
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, mxv;
    cin >> n >> mxv;
    
    vector<int> v(n + 1);
    vector<int> w(n + 1);
    for (int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i];
    
    // f[i][j]: 前 i 件放在最大容量为j的包里，最大价值
    vector<vector<int>> f(n + 1, vector<int>(mxv + 1, 0));
    
    // 构造二维dp数组
    for (int i = 1; i <= n; i++) {  // 对于前 1 ~ n 件
        for (int j = 1; j <= mxv; j++) {    // 从前 i 件放在最大容量为1的包里，到前 i 件放在最大容量为 mxv 的包里
            if (j >= v[i]) {   // j - v[i] >= 0，前 i - 1件物品放入容量为 j - v[i]的背包中，同时第i件可放可不放。
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);  
            }  
            else {  // j < v[i]背包全部容量都不够第i件物品的体积，必然不可放入
                f[i][j] = f[i  - 1][j];
            }
        }
    }
    
    // 二维数组的构造过程也是逐步求解过程，数组最后一个值f[n][mxv]即为所求：对于前 n 件物品，放在容量为mxv的背包中的最大价值
    cout << f[n][mxv] << endl;
    return 0;
}

一维dp数组的空间优化

注意到二维dp的状态转移方程：

  • f[i][j] = f[i - 1][j]
  • f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])

不难发现，前 i 件物品的最大价值只与前 i - 1 件物品有关。对应在二维数组中，第 i 行的计算只与第 i - 1 行有关。
不妨维护一个一维数组放入前 i - 1 件物品在不同容量背包下的最大价值。计算前 i 件物品的时候，可以直接使用，并完成更新为前 i + 1 件物品的计算做准备。

在一维dp中，考虑前 i 个物品在不同体积背包下的最大价值。
可定义一维数组：f[j] $(1 <= j <= V)$

状态转移方程：
下面我们尝试将二维状态转移方程压缩至一维：
f[i][j] = f[i - 1][j] 可以直接等价于 f[j] = f[j]
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]) 则可以等价于：
f[j] = max(f[j], f[j - v[i]] + w[i])

对于前 i 件物品，在计算 f[j] 的时候，注意 f[j - v[i]] 的来源：
首先应该明确 f[j - v[i]] 来自于前 i - 1 件物品的计算，即上一层循环得到的一位dp数组;
其次，j 大于 j - v[i] ，因为 j - (j - v[i]) > 0 ;
那么，为了计算前 i 件物品的最大价值，我们在更新当前的一维dp数组的时候需要使用到上一次计算前 i - 1 件物品的dp数组。其中，使用到的 f[j - v[i]] 在 f[j] 前面。
那么，如果我们计算了 f[j] 的值，并且更新了 f[j] ，那么 随着 j 的增大，需要使用到 f[j] 的时候，上一层的信息已经被本层之前的计算覆盖了。
为了解决更新第 i 次dp数组而不影响使用第 i - 1 次数组信息的问题，我们可以从大到小遍历体积：

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
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, mxv;
    cin >> n >> mxv;
    
    vector<int> v(n + 1);
    vector<int> w(n + 1);
    for (int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i];
    
    vector<int> f(mxv + 1, 0);
    
    for (int i = 1; i <= n; i++) {  // 对于前 1 ~ n 件
        for (int j = mxv; j >= 1; j--) {    // 从前 i 件放在最大容量为mxv的包里，到前 i 件放在最大容量为 1 的包里
            if (j >= v[i])
                f[j] = max(f[j], f[j - v[i]] + w[i]);
            else 
                f[j] = f[j];
        }
    }
    
    cout << f[mxv] << endl;
    return 0;
}

事实上，不难看出只有当 j >= v[i] 时dp数组会更新，所以：
for (int j = mxv; j >= 1; j--) 可以进一步优化成
for (int j = mxv; j >= v[i]; j--)

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
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, mxv;
    cin >> n >> mxv;
    
    vector<int> v(n + 1);
    vector<int> w(n + 1);
    for (int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i];
    
    vector<int> f(mxv + 1, 0);
    

    for (int i = 1; i <= n; i++) {  // 对于前 1 ~ n 件
        for (int j = mxv; j >= v[i]; j--) {     // 从前 i 件放在最大容量为mxv的包里，到前 i 件放在最大容量为 1 的包里
                f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[mxv] << endl;
    return 0;
}

原题链接： AcWing 2. 01背包问题