设计一个网站重点是什么,免费门户网站源码,系部网站建设方案,上海招聘网最新招聘文章目录 前言代码思路 前言
总是感觉有点没有完全懂#xff0c;但是说起来的时候好像又懂一点点#xff0c;就是我现在的状态。
代码
二维的直接的版本
#includeiostream
#includealgorithmusing namespace std;const int N 1010;
int f[N][N];
int v[… 文章目录 前言代码思路 前言
总是感觉有点没有完全懂但是说起来的时候好像又懂一点点就是我现在的状态。
代码
二维的直接的版本
#includeiostream
#includealgorithmusing namespace std;const int N 1010;
int f[N][N];
int v[N],w[N];
int n,m;int main(){scanf(%d%d,n,m);for(int i1;in;i){scanf(%d%d,v[i],w[i]);}for(int i1;in;i){for(int j0;jm;j){f[i][j]f[i-1][j];if(jv[i]){f[i][j]max(f[i][j],f[i-1][j-v[i]]w[i]);}}}printf(%d\n,f[n][m]);return 0;
}思路
我们把二维的优化为一维的数组的方法就是滚动数组因为我们计算当前这个数组的元素的答案的时候只用到了前面一个元素的数值有点像斐波那契数列每次只用到了前面两个数字来求和这里甚至更加简单只用了前面一个数字。
另外为什么 j 那一层优化之后要从大到小枚举呢是因为假设我们从小到大来进行枚举枚举的答案一定是当前层的答案好吧其实不是很理解算了先记住吧就是假设想要优化为一维的那就需要在枚举体积的时候从最大的体积枚举到当前商品的体积枚举到当前商品的体积很好理解假设小于当前商品的体积背包放不下该物品。
难怪看到弹幕刷 orz 我之前一直难以理解现在突然懂了就是一个自己很难理解清楚的东西有一个人可以很清楚地很细致地讲解出来这确实很厉害很值得敬佩。虽然我还是有点点没理解清楚。
滚动数组的意思是用一个空间是 2 的数组比如说 a[0] 和 a[1] 然后 0 调用 1 然后 1 调用 0 然后 0 调用 1然后 1 调用 0 有点像是左脚踩右脚然后就能起飞的感觉。
一维优化之后的版本
#includeiostream
#includealgorithmusing namespace std;const int N1010;
int n,m;
int v[N],w[N];
int f[N];int main(){scanf(%d%d,n,m);for(int i1;in;i){scanf(%d%d,v[i],w[i]);}for(int i1;in;i){for(int jm;jv[i];j--){f[j]max(f[j],f[j-v[i]]w[i]);}}printf(%d\n,f[m]);return 0;
}写到这里突然有点顿悟为什么体积要从到到小枚举了假设我们从小到大进行枚举那么每次算的是一个比较小的数值的答案我们可以确定那个比较小的答案就是最大值吗是这个意思吗。好像不是这么回事算了不想了。就这样吧。
