01 背包

前言

总是感觉有点没有完全懂，但是说起来的时候好像又懂一点点，就是我现在的状态。
代码

二维的直接的版本

1. #include<iostream>
2. #include<algorithm>
4. using namespace std;
6. const int N = 1010;
7. int f[N][N];
8. int v[N],w[N];
9. int n,m;
11. int main(){
12.     scanf("%d%d",&n,&m);
13.     for(int i=1;i<=n;i++){
14.         scanf("%d%d",&v[i],&w[i]);
15.     }
16.    
17.     for(int i=1;i<=n;i++){
18.         for(int j=0;j<=m;j++){
19.             f[i][j]=f[i-1][j];
20.             if(j>=v[i]){
21.                 f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
22.             }
23.         }
24.     }
25.    
26.     printf("%d\n",f[n][m]);
27.     return 0;
28. }

复制代码

思绪

我们把二维的优化为一维的数组的方法就是滚动数组，因为我们盘算当前这个数组的元素的答案的时候，只用到了前面一个元素的数值，有点像斐波那契数列，每次只用到了前面两个数字来求和，这里甚至更加简单，只用了前面一个数字。
另外为什么 j 那一层优化之后要从大到小枚举呢，是因为，假设我们从小到大来进行枚举，枚举的答案肯定是当前层的答案，好吧，实在不是很明白，算了先记着吧，就是假假想要优化为一维的，那就需要在枚举体积的时候从最大的体积枚举到当前商品的体积，枚举到当前商品的体积很好明白，假设小于当前商品的体积，背包放不下该物品。
难怪看到弹幕刷 orz ，我之前一直难以明白，现在突然懂了，就是一个本身很难明白清楚的东西，有一个人可以很清楚地，很细致地讲解出来，这确实很厉害，很值得敬佩。虽然我还是有点点没明白清楚。
滚动数组的意思是，用一个空间是 2 的数组，比如说 a[0] 和 a[1] ，然后 0 调用 1 ，然后 1 调用 0 ，然后 0 调用 1，然后 1 调用 0 ，有点像是左脚踩右脚，然后就能腾飞的感觉。
一维优化之后的版本

1. #include<iostream>
2. #include<algorithm>
4. using namespace std;
6. const int N=1010;
7. int n,m;
8. int v[N],w[N];
9. int f[N];
11. int main(){
12.     scanf("%d%d",&n,&m);
13.     for(int i=1;i<=n;i++){
14.         scanf("%d%d",&v[i],&w[i]);
15.     }
16.    
17.     for(int i=1;i<=n;i++){
18.         for(int j=m;j>=v[i];j--){
19.             f[j]=max(f[j],f[j-v[i]]+w[i]);
20.         }
21.     }
22.     printf("%d\n",f[m]);
23.    
24.     return 0;
25. }

复制代码

写到这里突然有点顿悟为什么体积要从到到小枚举了，假设我们从小到大进行枚举，那么每次算的是一个比较小的数值的答案，我们可以确定谁人比较小的答案就是最大值吗，是这个意思吗。好像不是这么回事，算了，不想了。就如许吧。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。