研究生课程系列文章参见索引《在信科的那些课》
之前整理了屈奶奶讲的背包问题,感谢cyh24童鞋留言,传我一份武林秘籍《背包问题九讲》,实践了一下文档里对空间复杂度的改进。
0-1背包问题
通过之前的分析,Fk(y) 表示只允许装前k 种物品,背包总重不超过y 时背包的最大价值。得到0-1背包的递推公式和边界条件:
对空间的优化主要在Fk(y),原本我们用两个循环实现:
for(int k=1;k<=N;k++){
for(int y=1;y<=B;y++){
if(y-w[k-1]<0){
F[k][y]=F[k-1][y];
tagi[k][y]=tagi[k-1][y];
}
else{
//允许装入k件物品,价值的两种情况:
//不装第k件物品或至少装1件第k件物品
F[k][y]=F[k-1][y]>F[k][y-w[k-1]]+v[k-1] ? F[k-1][y]:(F[k][y-w[k-1]]+v[k-1]);
tagi[k][y]=F[k-1][y]>F[k][y-w[k-1]]+v[k-1]?tagi[k-1][y]:k;
}
}
}
实际并一定不需要F[N][B]的空间,如果内层循环以B...0递推,即下面的形式:
for(int k=1;k<=N;k++){
for(int y=B;y>0;y--){
F[y]=max{F[y],F[y-w[i]]+v[i]};
}
}
因为是以B...0倒序递推,则F[y]此时就是F[k-1][y]的值,而F[y-w]还未改变,仍为F[k-1][y-w]的值。因此可以用一维数组存储原来的优化函数信息。代码如下:
void ZeroOnePack(int F[],int tagi[],int v, int w,int k){
for(int i=B;i>0;i--){
if(i-w>=0&&F[i]<=(F[i-w]+v)){
F[i]=F[i-w]+v;
tagi[i]=k;
}
}
}
完全背包问题
再看完全背包问题,即每个物品有无限件,不限每个物品装入的个数。得到递推关系和边界条件:
递归公式最主要的区别是Fk(y-wk)+vk,而非原来的Fk-1(y-wk)+vk,即物品可以在前k件中继续挑选。用一维数组时希望此时F[y]的数值即为F[k-1][y]的数值,而F[y-w]的数值为改变之后的F[k-1][y-w]的数值。因此我们可以用顺序0...B(而非逆序B...0)实现:
for(int k=1;k<=N;k++){
for(int y=0;y>B;y++){
F[y]=max{F[y],F[y-w[i]]+v[i]};
}
}
具体代码如下:
void CompletePack(int F[],int tagi[],int v, int w,int k){
//F[i]=F[i]>(F[i-w]+v)?F[i]:(F[i-w]+v);
//tagi=F[i]>(F[i-w]+v)?tagi:tagi+1;
for(int i=1;i<=B;i++){
if(i-w>=0&&F[i]<=(F[i-w]+v)){
F[i]=F[i-w]+v;
tagi[i]=k;
}
}
}
测试用例
前面是0-1背包和完全背包的内层循环,还需要一个外层循环调用:
void Knapsack(int F[],int tagi[][B+1],int v[], int w[]){
for(int i=0;i<B+1;i++){
F[i]=tagi[0][i]=0;
}
for(int i=0;i<N+1;i++)
tagi[i][0]=0;
for(int i=0;i<N;i++){
for(int j=0;j<B+1;j++)
tagi[i+1][j]=tagi[i][j];
//0-1背包
ZeroOnePack(F,tagi[i+1],v[i],w[i],i+1);
//完全背包
//CompletePack(F,tagi[i+1],v[i],w[i],i+1);
}
}
还有
之前文章的例子来测试,输出结果:
分享到:
相关推荐
内容为Java专业,算法设计关于背包问题的代码,以及贪心算法。
算法课程设计 背包问题 0/1背包问题 实现算法课程设计 背包问题 0/1背包问题 实现 算法课程设计 背包问题 0/1背包问题 实现算法课程设计 背包问题 0/1背包问题 实现 算法课程设计 背包问题 0/1背包问题 实现 算法...
背包问题.本算法比较清晰,易读。...背包问题是比较经典的算法。很具有代表性。在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
实验目的:0/1背包问题的回溯算法设计 实验原理:回溯算法设计。 实验要求:基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的...
用贪心算法实现背包问题 集SSH框架,android,行业资讯,数据库,web开发,设计模式希望大家一起分享
关于背包问题的源代码,包括贪心算法和动态算法
算法设计与分析、课程设计报告、普通背包、棋盘覆盖
算法设计与分析课程的背包问题算法设计与分析课程的背包问题算法设计与分析课程的背包问题算法设计与分析课程的背包问题算法设计与分析课程的背包问题算法设计与分析课程的背包问题
算法设计的零一背包问题的设计,用VC++编程实现,大家可以看看提一下意见
算法分析与设计实验报告书:回溯算法之背包问题。 实验目的和要求 (1)掌握回溯法的设计思想; (2)掌握解空间树的构造方法,以及在求解过程中如何存储求解路径; (3)考察回溯法求解问题的有效程度。 (4)设计...
C++应用贪心算法求解背包问题,可用于算法课程设计答辩。
01背包问题,VC编程,算法设计中的非常典型的问题希望对大家有用
动态规划算法 0-1背包问题 各种各样的背包问题的原理分析
0-1背包问题 0-1背包问题 0-1背包问题 0-1背包问题
该系统对0-1背包算法的实现过程进行了软件模拟,效果良好。
算法设计,0-1背包问题,用java编写的贪心算法实现0-1背包问题。。
本实验描述了算法分析课程实验中的背包问题,其中包括贪心算法、动态规划和回溯算法的概念和基本思想,分析并掌握"0-1"背包问题的三种算法,并分析其优缺点
计算机算法设计与分析中所研究的背包问题。查找最优解。