欢迎来到天天文库
浏览记录
ID:38181339
大小:42.50 KB
页数:4页
时间:2019-05-24
《回溯算法之0-1背包问题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、1、实验目的(1)掌握回溯法设计策略。(2)通过0-1背包问学习回溯法法设计技巧2.实验内容源程序:#includeusingnamespacestd;doublec;//背包容量intn;//物品数doublew[100];//物品重量数组doublep[100];//物品价值数组doublecw=0;//当前重量doublecp=0;//当前价值doublebestp=0;//当前最优值doublebound(inti){doublecleft,b;//计算上界cleft=c-cw;//剩余容量b=cp;//以物品单位重量价值
2、递减序装入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//装满背包if(i<=n)b+=p[i]*cleft/w[i];returnb;}voidBacktrack(inti){if(i>n){if(cp>bestp)bestp=cp;return;}if(cw+w[i]<=c)//搜索左子树{cw+=w[i];cp+=p[i];Backtrack(i+1);cp-=p[i];cw-=w[i];}if(bound(i+1)>bestp)//搜索右子树Backtrack(i+1);}doubl
3、eKnapsack(doublepp[],doubleww[],doubled){inti;doubleTP=0,TW=0;cw=0.0;cp=0.0;bestp=0.0;//计算所有物品的重量及价值for(i=1;i<=n;i++){TP=TP+pp[i];TW=TW+ww[i];}if(TW<=d)//所有物品装入背包bestp=TP;else{Backtrack(1);}returnbestp;};intmain(){inti,j;doublet,a,x[100];cout<<"请输入物品种类数和最大载重量:"<>n;cin
4、>>c;cout<<"请输入各物品重量:"<>w[i];cout<<"请输入各物品价值:"<>p[i];//排序for(i=1;i<=n;i++)x[i]=p[i]/w[i];for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)if(x[i]5、//////////////////////Knapsack(p,w,c);cout<<"结果:"<
5、//////////////////////Knapsack(p,w,c);cout<<"结果:"<
此文档下载收益归作者所有