概览
背包问题，就是给定你一些背包和一些物品，通常情况下给出物品的价值和体积，再在不同类型中给定不同的限制条件，最后往往希望你给出能获得的最大价值。
01背包
要求
限制背包的最大体积，给出每种物品的体积和价值，每种物品只有一个，求能获得的最大价值。
解决
基础版
考虑状态dp[i][j]，表示在前i件物品中有j的体积可以获得的最大利润。
对于每个dp[i][j]，有两种情况：选不选第j件物品。
- 若选，则dp[i][j]=dp[i-1][j-v[i]]+w[i]，表示在前i-1个物品中，若有j-当前物品体积的剩余体积，还能获得的最大价值，加上当前物品的价值。
- 若不选，则dp[i][j]=dp[i-1][j]，表示就不说了。
- 两者取最大值，作为在前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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e3+3;
int n,nv;
int v[N],w[N];
int f[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j]=f[i-1][j];
if(j>=v[i])f[i][j]=max(f[i-1][j-v[i]]+w[i],f[i][j]);
}
}
cout<<f[n][m]<<endl;
return 0;
}
|
优化版
毕竟是二维背包，还是有点好空间，这里就思考把它转化成一维：
首先，可以省略的肯定是第一维。这里如下推导：
对于对于当前循环而言，dp中储存的其实就是i-1的值，所以第一个维度没有必要，考虑使用滚动数组实现优化。
特殊地，我们应该从后往前循环，因为新的dp中会用到它前面的值，我们必须保证它前面的值是前i-1个的dp值。若从前往后循环，它前面的值就是更新之后的值了。
另外，w[i]之前的体积，我们可以不操作，它们就默认还是i-1的值，仍然符合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
using namespace std;
const int N=1e3+3;
int n,nv;
int v[N],w[N];
int f[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];
for(int j=m;j>=v[i];j--){
f[j]=max(f[j-v[i]]+w[i],f[j]);
}
}
cout<<f[m]<<endl;
return 0;
}
|
是不是很简单~
完全背包
要求
限制背包的最大体积，给出每种物品的体积和价值，每种物品有无限个，求能获得的最大价值。
解决
完全背包和01背包很像的，所以就接着01背包讲了。
基础版
这里与01背包唯一的区别就是每种物品可以放多个，并且没有数量限制。怎么解决呢？事实上，我们只需要更改一下状态转移方程就行了（废话）
一共有哪些选法呢？选0个、1个、2个……直到背包装不下了为止。
那么方程就是这样的：
dp[i][j]=max(dp[i][j],dp[i-1][j-kv[i]]+kw[i])
其中k就是选j的个数，枚举即可。还是很简单对吧。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<bits/stdc++.h>
using namespace std;
const int N=1e3+3;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];
for(int j=0;j<=m;j++){
for(int k=0;k*v[i]<=j;k++){
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);
}
}
}
cout<<f[n][m];
return 0;
}
|
优化版
不只是空间，这次时间复杂度也上去了，所以优化是必须的。
我们先枚举一些情况来找规律：
f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,f[i-1][j-3v]+3w,…)
f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+2w,…)
f[i][j-2v]=max(f[i-1][j-2v],f[i-1][j-3v]+w,…)
那么规律就很明显了：
f[i][j]=max(f[i-1][j], f[i][j-v]+w)
这是一种规律上的理解，接下来说一个理解性的理解（是我个人理解的理解，所以如果你不理解也请你理解理解）
既然一个物品有多个，那么就是说当前物品可以选多个，因此不管之前选没选过都可以再选（不同于01），故而j空间获取的最大值范围就广了，不只是前i-1件可以获得的最大值，而是前i件可以获得的最大值（包括i），因此就可以由f[i][j-v[i]]+w[i]获得。
这样的话，就包含了含有多个i的情况，并且自动地在所有可行情况中取了最大值。
以上都相当于优化了k循环，但后就是喜闻乐见地优化i循环。
具体过程就不说了，值得一提的是：记得从前往后循环，因为这次需要的dp值是第i次的，需要先进行更新。同样的，由上方方程可以得到，直接省略v[i]之前的状态是可行的，它们将默认被赋值为i-1的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
using namespace std;
const int N=1e3+3;
int n,m;
int v[N],w[N];
int f[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];
for(int j=v[i];j<=m;j++){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
return 0;
}
|
多重背包
要求
限制背包的最大体积，给出每种物品的体积和价值，每种物品只有特定数量个，求能获得的最大价值。
解决
鉴于上面已经有了两个基础类型的铺垫，这里就不卖关子了，直接开始：
基础版
和完全背包差不多，在k哪里多加一个限制：k≤s[i]（i的个数）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<bits/stdc++.h>
using namespace std;
const int N=1e3+3;
int n,m;
int v[N],w[N],s[N];
int f[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i]>>s[i];
for(int j=0;j<=m;j++){
for(int k=0;k*v[i]<=j&&k<=s[i];k++){
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);
}
}
}
cout<<f[n][m];
return 0;
}
|
是不是更简单了~
优化版
二进制优化
这里呢，我们使用二进制优化，含有倍增思想。
我们可以把每个物品的个数分成几组，每个组个数如下：
20, 21, 22, 23, …, 2k, c
20+21+22+23+…+2k+c=s
要求c<2k+1
那么，我们就可以凑出0~s里面所有的数了（不加c可以凑出0~2k+1-1里的所有数，加c可以凑出c~s里的所有数，又因c<2k+1，所以满足条件）。
因此，我们只需要让k遍历这些组即可，可以凑出所有情况，那么就一定能求得正确的最大值。
然后呢，我们的问题就变成了解决一个大小为nlogs的01背包（倍增性质，2i每个都只需要选一次，就能凑出所有可能）
最后顺便把第一维优化了，这个不必多说。
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
34
35
36
37
38
39
40
41
42
| #include<bits/stdc++.h>
using namespace std;
const int N=12000,M=2005;
int n,m;
int v[N],w[N],f[N];
int init(){
int cnt=0;
int a,b,s;
for(int i=1;i<=n;i++){
cin>>a>>b>>s;
int k=1;
while(k<=s){
cnt++;
v[cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
}
if(s){
cnt++;
v[cnt]=a*s;
w[cnt]=b*s;
}
}
return cnt;
}
int main(){
cin.tie(0);
cin>>n>>m;
n=init();
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
return 0;
}
|
单调队列优化
基础的话只学习二进制优化应该就够（呛）了，所以就不放单调队列优化了，有时间写一篇提高版的话可以顺带着提一嘴。
分组背包
要求
限制背包的最大体积，给出每种物品的体积和价值，其中分成了很多组，每组物品最多只选一个，求能获得的最大价值。
解决
其实很简单啊，我们把每一组都视作一个物品，但是这个物品有很多种vw组合，然后直接用01背包做就行了。
可能有一点点抽象，但是看了代码就茅塞顿开。这部分比二进制优化好做多了
这里的优化就是最简单的滚动数组，不做解释。
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;
const int N=105;
int n,m;
int s[N],v[N][N],w[N][N];
int f[N];
int main(){
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int k=1;k<=s[i];k++){
cin>>v[i][k]>>w[i][k];
}
for(int j=m;j>=0;j--){
for(int k=1;k<=s[i];k++){
if(v[i][k]<=j){
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
}
}
}
}
cout<<f[m];
return 0;
}
|
完结撒花o(￣︶￣)o