背包问题
常见的背包问题如下:
- 01背包:每个物品只有一个
- 完全背包:每个物品数量无限
- 多重背包:不同物品数量不同
01背包
题目描述:
有N件物品和一个最多能承受重量为W的背包，第i件物品的重量是weight[i]，得到的价值是value[i]，每件物品只能用一次，求解将哪些物品装入背包后物品价值的总和最大？
问题分析:
标准的01背包问题,首先可以尝试使用暴力方法解决:
每个物品都有2种选择:要么不选取,要么选取,使用0或1来表示这两种状态,因此得名01背包
对每个物品的2种选择会导致不同的效果,因此可以使用回溯法来搜索所有的情况,时间复杂度为O(2n),n为物品数量.
这个时间复杂度是无法接受的,下面分析使用动态规划解决.
二维DP解法
背包问题,涉及背包的大小和物品的选取以及重量和价值.
对第i个物品而言,需要考虑当前背包是否能放下该物品,即背包当前剩余的容量要大于等于该物品的重量weight[i].
为同时考虑背包大小和物品数量及选取,我们使用二维数组dp[][],其中dp[i][j]表示将前i件物品(不一定全部都选择)装进大小(限重)为j的背包所能获得的最大价值.
根据动态规划的思想,我们在考虑状态[i,j](因为这里是二维DP)时,只假设前[i-1,j],[i,j-1]等等所有状态均已求出最优解,而无需关心如何纠结求解,只是假设已经获得该状态.
那么对于求解这里当前的dp[i][j],有如下2种情况:
- 如果不选择物品i,那么
dp[i][j]就等于使用前(i−1)个物品来装大小为j的背包的最大价值,即dp[i-1][j]
- 如果选择物品i,那么就要保证背包
至少还能够装下该物品,即背包已装满的重量至多需为(j−weight[i]),dp[i][j]就等于使用前(i−1)个物品来装大小为(j−weight[i])的背包的最大价值,再加上当前物品i的价值value[i],即dp[i-1][j-weight[i]]+value[i]
注意情况2中,由于显然我们知道,无论如何,想要总价值最大,那么背包的容量自然越大越好,所以说"背包已装满的重量至多需为(j−weight[i])",也就是说将物品i放入后,恰好放满,此时背包利用率为100%,显然总价值最高(注意此时与物品的性价比无关).
上面的2种情况均能计算出一个价值,因此最终的dp[i][j]取二者的max值,这即为状态转移方程:
dp[i][j]=max(dp[i−1][j],dp[i−1][j−weight[i]]+value[i])
再考虑初始条件:
-
当背包大小为0时,选取任何物品的总价值自然为0,即dp[i][0]全部为0
-
当选取第一个物品时,装不下该物品的背包dp[0][0-(wight[0]-1)]均为0,其他能装下dp[0][wight[0]-W]的均为value[0]
-
事实上根据状态转移方程得知,各数值均从左上角推导得来,所以其余元素可以不初始化,不过默认初始化为0也可(注意求max最好用0填充)
最后就是二重循环的遍历顺序,究竟是先(外层)遍历物品,还是先遍历背包大小.
事实上2种写法均可,根据状态转移方程可知并不影响递推计算.但是二者意义不同.
先遍历物品再遍历背包大小比较容易理解.
-
遍历物品优先:
在这种方式下,外层循环遍历物品,内层循环遍历背包容量.这样,对于每个物品,我们考虑其是否加入背包,然后更新所有可能的背包容量.
-
遍历背包大小优先:
在这种方式下,外层循环遍历背包容量,内层循环遍历物品,这样,对于每个背包容量,我们逐个考虑加入物品,然后更新所有可能的物品.
C++代码如下:
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
|
#include <iostream>
#include <vector>
#include <algorithm>
#define MAXN 100
#define MAXM 1000
using namespace std;
int main() {
int m, n;
cin >> m >> n;
vector<int> w(n + 1);
vector<int> v(n + 1);
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 0; i < n; i++) {
cin >> w[i] >> v[i];
}
for (int i = w[0];i <= m;++i) {
dp[0][i] = v[0];
}
for (int i = 1;i < n;++i) {
for (int j = 0;j <= m;++j) {
if (j < w[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
cout << dp[n - 1][m];
return 0;
}
|
一维DP优化
根据二维DP的状态转移方程可知,dp[i][j]的推导仅与dp[i - 1][j]和dp[i - 1][j - w[i]],二者都在上一行,并且最终的答案仅在最后一行,无需关心前面的各行.
因此,很容易可以想到,将二维DP数组优化为仅有一行的一维数组,或者叫"滚动数组".
我们直接用一维dp[],其中dp[j](注意下标为j)代表容量为j的背包能获得的最大价值.
状态转移方程很简单,如下:
dp[j]=max(dp[j],dp[j−weight[i]]+value[i])
至于初始化dp[],由于状态转移方程使用max,又因为价值都是正数,因此全部初始化为0.
与二维不同,一维优化的遍历顺序完全不同,(伪)代码如下:
1
2
3
4
5
| for(int i=0;i<n;++i){
for(int j=m;j>=weight[i];--i){
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
}
}
|
一维DP中,背包容量必须从大到小遍历,否则就会导致物品i被重复加入多次(考虑物品0的重量为1,价值为15,正序遍历对dp[1],dp[2]的影响—计算dp[2]时,该物品被加入了2次,错误).
换句话说,如果顺序遍历,使用当前物品更新各状态时,各状态(当前行各元素)会发生重叠,导致求解错误.
而二维DP中,每一行都是由上一层计算得来,不会影响本层.
另一方面,必须是先遍历物品在外,然后再遍历背包大小在内.如果背包大小在外层,那么每个dp[j]就只会放入一个物品(注意理解dp[j]的定义).
C++代码:
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
|
#include <iostream>
#include <vector>
#include <algorithm>
#define MAXN 100
#define MAXM 1000
using namespace std;
int main() {
int m, n;
cin >> m >> n;
vector<int> w(n + 1);
vector<int> v(n + 1);
vector<int> dp(m + 1, 0);
for (int i = 0; i < n; i++) {
cin >> w[i]>>v[i];
}
for (int i = 0;i < n;++i) {
for (int j = m;j >= w[i];--j) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[m];
return 0;
}
|
01背包-剩余空间最小问题
题目描述:
有N件物品和一个最多能装体积为W的背包，第i件物品的体积为w[i],求解将哪些物品装入背包后,背包剩余空间最小,输出该最小值.
问题分析:
与01背包不同,此时求解的不再是价值,而是仅考虑能否装下,求解最小的剩余空间,也就是要求如何能够装下最大体积的物品.需要注意的是,本题不能使用贪心,很容易举出反例.
根据分析,我们将问题转化为"如何使装入体积最大",最后用总体积减去该最大体积即可.
事实上,该问题某种程度上可以理解为此时的value[]就是weight[],因此与常规01背包的区别仅仅是将v[]直接用w[]替换,并用m减去最终结果即可,其他完全相同!
下面的推理完全类似于01背包:
二维DP解法
使用二维dp[][]数组,其中dp[j]表示体积为j的背包能装下的最大体积.
状态转移方程:
dp[i][j]=max(dp[i−1][j],dp[i−1][j−weight[i]]+weight[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
|
#include <iostream>
#include <vector>
#include <algorithm>
#define MAXN 100
#define MAXM 1000
using namespace std;
int main() {
int m, n;
cin >> m >> n;
vector<int> w(n + 1);
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 0; i < n; i++) {
cin >> w[i];
}
for (int i = w[0];i <= m;++i) {
dp[0][i] = w[0];
}
for (int i = 1;i < n;++i) {
for (int j = 0;j <= m;++j) {
if (j < w[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + w[i]);
}
}
cout << dp[n - 1][m];
return 0;
}
|
一维DP优化
使用一维dp[]数组,其中dp[j]表示体积为j的背包能装下的最大体积.
对于每一个物品i,仍然考虑选或不选,则有2种情况:
- 不选物品i,f[j]不变
- 选物品i,f[j]=f[j-w[i]]+w[i]
则有状态转移方程:
f[j]=max(f[j],f[j−w[i]]+w[i])
其实同样,只是将v[i]替换为w[i],然后输出结果为(背包总大小W-f[W])即可.
C++代码:
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 <iostream>
#include <vector>
#include <algorithm>
#define MAXN 100
#define MAXM 1000
using namespace std;
int main() {
int m, n;
cin >> m >> n;
vector<int> w(n + 1);
vector<int> dp(m + 1, 0);
for (int i = 0; i < n; i++) {
cin >> w[i];
}
for (int i = 0;i < n;++i) {
for (int j = m;j >= w[i];--j) {
dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
}
}
cout << m-dp[m];
return 0;
}
|
完全背包
题目描述:
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包中物品价值的总和最大。
问题分析:
借鉴01背包,使用f[i][j]来代表状态(见前)
朴素做法
对第i件物品,枚举其选了多少次(个)来转移,时间复杂度为O(n3).状态转移方程如下:
f[i][j]=k=0max+∞(f[i−1][j−k×w[i]]+k×v[i])
可以考虑如此优化:
由于f[i][j−w[i]]已经由f[i−1][j−2×w[i]]更新过,也就是说f[i][j−w[i]]已经是充分考虑了第i件物品所选次数后的结果,因此,可以将状态转移方程优化为:
f[i][j]=max(f[i−1][j],f[i−1][j−w[i]]+v[i])
一维优化
同样,可以将二维优化为一维.
但与01背包不同,该问题中每个物品都有无限多个,因此首先遍历顺序就要改变.
在01背包的一维优化的代码中,内层循环(背包大小)必须从大到小遍历,以保证每个物品只被添加一次;而在完全背包中,该物品是可以被添加多次的,因此要从小到大遍历.
代码如下:
1
2
3
4
5
| for (int i = 0;i < n;++i) {
for (int j = w[i];j <= m;++j) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
|
另外,在完全背包的一维DP中,两层循环的顺序其实并不影响结果(但是诸如"装满背包的方式有几种"这样的问题就有区别了).
C++代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <bits/stdc++.h>
using namespace std;
unsigned long long f[10000001];
int main() {
int m, n;
cin >> m >> n;
unsigned long long w, v;
for (int i = 0;i < n;++i) {
cin >> w >> v;
for(int j=w;j<=m;++j){
f[j]=max(f[j],f[j-w]+v);
}
}
cout << f[m];
return 0;
}
|
注:零钱兑换题目是完全背包,但是求的是方案的数目.外物品内背包是组合数,外背包内物品是排列数.
wechat
alipay