回溯算法之0-1背包问题

《回溯算法之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<<"结果："<