01 背包
前言总是感觉有点没有完全懂，但是说起来的时候好像又懂一点点，就是我现在的状态。
代码
二维的直接的版本
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int f;
int v,w;
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&v,&w);
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
f=f;
if(j>=v){
f=max(f,f]+w);
}
}
}
printf("%d\n",f);
return 0;
}
思绪
我们把二维的优化为一维的数组的方法就是滚动数组，因为我们盘算当前这个数组的元素的答案的时候，只用到了前面一个元素的数值，有点像斐波那契数列，每次只用到了前面两个数字来求和，这里甚至更加简单，只用了前面一个数字。
另外为什么 j 那一层优化之后要从大到小枚举呢，是因为，假设我们从小到大来进行枚举，枚举的答案肯定是当前层的答案，好吧，实在不是很明白，算了先记着吧，就是假假想要优化为一维的，那就需要在枚举体积的时候从最大的体积枚举到当前商品的体积，枚举到当前商品的体积很好明白，假设小于当前商品的体积，背包放不下该物品。
难怪看到弹幕刷 orz ，我之前一直难以明白，现在突然懂了，就是一个本身很难明白清楚的东西，有一个人可以很清楚地，很细致地讲解出来，这确实很厉害，很值得敬佩。虽然我还是有点点没明白清楚。
滚动数组的意思是，用一个空间是 2 的数组，比如说 a 和 a ，然后 0 调用 1 ，然后 1 调用 0 ，然后 0 调用 1，然后 1 调用 0 ，有点像是左脚踩右脚，然后就能腾飞的感觉。
一维优化之后的版本
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
int v,w;
int f;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&v,&w);
}
for(int i=1;i<=n;i++){
for(int j=m;j>=v;j--){
f=max(f,f]+w);
}
}
printf("%d\n",f);
return 0;
}
写到这里突然有点顿悟为什么体积要从到到小枚举了，假设我们从小到大进行枚举，那么每次算的是一个比较小的数值的答案，我们可以确定谁人比较小的答案就是最大值吗，是这个意思吗。好像不是这么回事，算了，不想了。就如许吧。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]