网站谁做的,营销类网站建设,wordpress插件去除版权,绵阳市城市建设档案馆网站C 01背包问题 问题简单描述 有#xff2e;件物品和总容量为#xff37;的背包#xff0c;每件物品只能使用一次。 设第#xff49;件物品的价值为#xff56;(i),第#xff49;件物品的重量为 w(i)。 求解: 问应将哪些物品放入背包中#xff0c;在不超过最大容量的情况下… C 01背包问题 问题简单描述 有件物品和总容量为的背包每件物品只能使用一次。 设第件物品的价值为(i),第件物品的重量为 w(i)。 求解: 问应将哪些物品放入背包中在不超过最大容量的情况下使得总价值最大 算法1实现
#includealgorithm
#includestdio.h
#includetime.h
#includestdlib.h
using namespace std;
const int MAXL 1e5;
int w[MAXL1],v[MAXL1],f[MAXL1][MAXL1];
clock_t start ,stop;
int main(){int N,W;scanf(%d %d,N,W);for(int i 1;i N;i){scanf(%d %d,w[i],v[i]);}start clock();for(int i 1; i N;i ){for(int j 1;j W;j ){if (j w[i]) f[i][j] f[i-1][j];else f[i][j] max(f[i-1][j],f[i-1][j-w[i]]v[i]);}}stop clock();printf(%d,f[N][W]);printf(\n遍历时间%fs,(double(stop - start))/CLOCKS_PER_SEC);return 0;
}其为两种转移方式 1.当前容量小于第 i 件物品的重量 2.当前容量大于第 i 件物品的重量则选择使得价值最大的物品
运行结果截图 算法2实现
空间改善后的算法
#includebits/stdc.h
using namespace std;
const int L 1e5;
int v[L1],w[L1],f[L1];
clock_t start ,stop;int main(){int N,W;scanf(%d %d,N,W);for(int i 0; i N ; i)scanf(%d%d,w[i],v[i]);memset(f,0,sizeof(f));start clock();for(int i 0;i N; i){for(int j V;j 0; j--){if ( w[i] j )f[j] max(f[j],f[j-w[i]]v[i]);}}printf(%d,f[W]);stop clock();printf(\n遍历时间%.4fs,(double(stop - start))/CLOCKS_PER_SEC);return 0;
}运行结果截图 核心代码详解
首先需要理解状态转移公式 f[j] max(f[j],f[j-w[i]]v[i]); 这里的数组代表的含义为当前价值对于该数组其下标代表的含义为当前容量。 max函数里两项为两种选择我们就是需要找到最大价值情况的背包。 第一种选择为不取第件物品放入背包 第二种选择为取第件物品放入背包 对于第一种选择当前的容量应该不变当前的价值也不发生变化。 对于第二种选择当前容量需要减少第件的重量以及当前价值需要增加相应的价值。 对于遍历首先最外层循环即为遍历每件物品选择其中一些物品放入背包对于第二层循环即从当前背包的最大容量逐渐递减遍历每次当前价值与上一次的价值进行比较选择相应容量下的最大价值覆盖对于该层的 if 语句只是边界条件即当前背包容量必须大于等于需要放入的物品重量防止溢出。 for(int i 0;i N;i){for(int j V;j 0;j--){if (w[i] j )f[j] max(f[j],f[j-w[i]]v[i]);}}最终输出的结果为
printf(%d,f[V]);为什么会是数组最后一个 通过算法的迭代此时它表示的容量就是的最大价值。
