今天学习了简单的几个背包问题，分别是01背包、完全背包、多重背包，在此总结一下我对背包问题的理解和优化的思路。
01背包：
01背包思路很简单一开始我写的是二维，很好理解，01背包问题的关键就是什么时候选时候不选，f[i][j]就是在前i个物品，j个大小内最大能装的数量，假设f[i-1][j]也就是对于容量位j的情况下前i-1个物品的最优解已经确立，对于f[i][j]的最优解只需要看第i个物品选还是不选就行了。
不选就是f[i-1][j]选就是f[i-1][j-v[i]]+m[i]，选择两者中最大的就行，不过进行比较前的先让f[i][j]=f[i-1][j]然后进行判断j>=v[i],dddd，f[0][0]的情况是确立的为0，然后递推就可以了，最后从f[n][0~v]取最大值就是答案。
代码：
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<stdio.h>#include<string.h>
#include<algorithm>
using namespace std;
int N,V;
int f[1010][1010];
int v[1010],m[1010];
int main(){
int res=0;
scanf("%d %d",&N,&V);
for(int i=1;i<=N;i++){
scanf("%d %d",&v[i],&m[i]);
}
for(int i=1;i<=N;i++){
for(int j=0;j<=V;j++){
f[i][j]=f[i-1][j];
if(j>=v[i])
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+m[i]);
}
}
int ans=0;
for(int i=0;i<=V;i++) ans=max(ans,f[N][i]);
printf("%d",ans);
return 0;
}
|
优化：
二维很好理解但是开的数组很大，所以把它优化为一维，一般优化的时候我们做等价变化，把一维全部一去然后会发现核心判断变成了这样
1
2
3
4
5
| for(int i=1;i<=N;i++){
for(int j=0;j<=V;j++){
f[j]=max(f[j],f[j-v[i]]+m[i]);
}
}
|
但其实很容易就发现问题，因为我们一开始写的是f[i][j]和f[i-1][j-v[i]]，但到这里就会发现其实不是i-1]而是i,为了解决这个问题只需要从大到小去推就行了，
其实很好理解，外部循环我们是从小到大的，内部从大到小，j-v[i]一定小于j所以在内部的循环一定是先进行j在进行j-v[i]，所以现在的j-v[i]是没有更新过的，
也就是f[i-1]的情况。最后只需要输出f[V]就可以了因为一开始都初始化为0,f[V]的意思就是容量为v的最优解，即使最优解实际容量不是v，可能是k，也可以
从f[k]的情况转移到f[v]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int f[1005];
int main()
{
int n,m,x,y;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>x>>y;
for(int j=m;j>=x;j--){
f[j]=max(f[j-x]+y,f[j]);
}
}
cout<<f[m];
return 0;
}
|
完全背包：
完全背包和01背包看似只有内部循环的顺序不同但其实对于这个的理解还是要很深的，先上代码。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int N,V;
int v[1010],w[1010];
int f[1010];
int main(){
scanf("%d %d",&N,&V);
for(int i=1;i<=N;i++){
scanf("%d %d",&v[i],&w[i]);
}
for(int i=1;i<=N;i++){
for(int j=v[i];j<=V;j++){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
printf("%d",f[V]);
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| 首先先分析，完全背包和01背包的区别就是可以选多次，所以对于f[i][j]就不再是选与不选两种情况而是选k种与不选的多种情况，对于不选还是f[i-1][j]，
选一种就是f[i-1][j-v[i]]+w[i]，两种就是f[-1][j-2v[i]]+2w[i]...f[i-1][j-kv[i]]+kw[i]，也就是容量上限的时候，其实对于这种很容易就可以想到再加一个循环枚举0
到k的情况然后取最大值就可以，但是也很容易就想到这样会超时，而之所以代码只进行了一次比较是有很大原因的。
继续分析，对于f[i][j-w[i]]来说，就相当于是
f[i-1][j-v[i]] f[i-1][j-2v[i]]+w[i] ... f[i-1][j-k+1v[i]]+kw[i]
而f[i][j]则是f[i-1][j] f[i-1][j-v[i]]+w[i] f[-1][j-2v[i]]+2w[i] ... f[i-1][j-kv[i]]+kw[i]
很容易就看出f[i][j]其实就是f[i][j-v[i]]加上w[i]与f[i-1][j]的最大值。然后我们是从小到大去递，所以一开始的f[j]是没有更新的f[j]也就是f[i-1][j]，而j-v[i]比j小所以
f[j-v]是已经更新过的也就是f[i][j-v],最后输出f[v]。
|
