回溯算法解决0-1背包问题.doc

《回溯算法解决0-1背包问题.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法分析与设计》实验报告2015-2016年第2学期实验班级：学生姓名：学号：指导老师：信息工程学院实验项目名称：回溯算法解决0-1背包问题实验日期：2016年5月18日一、实验类型：验证性□设计性二、实验目的掌握0—1背包问题的回溯算法三、实验内容及要求给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?四、实验步骤#includeusingnamespacestd;classKnap{friendintK

2、napsack(intp[],intw[],intc,intn);public:voidprint(){for(intm=1;m<=n;m++){cout<

3、t*x;//当前解};intKnap::Bound(inti){//计算上界intcleft=c-cw;//剩余容量intb=cp;//以物品单位重量价值递减序装入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//装满背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;}voidKnap::Backtrack(inti){if(i>n){if(bestp

4、bestp=cp;}return;}if(cw+w[i]<=c)//搜索左子树{x[i]=1;cw+=w[i];cp+=p[i];Backtrack(i+1);cw-=w[i];cp-=p[i];}if(Bound(i+1)>bestp)//搜索右子树{x[i]=0;Backtrack(i+1);}}classObject{friendintKnapsack(intp[],intw[],intc,intn);public:intoperator<=(Objecta)const{return(d>=a.d);}

5、private:intID;floatd;};intKnapsack(intp[],intw[],intc,intn){//为Knap::Backtrack初始化intW=0;intP=0;inti=1;Object*Q=newObject[n];for(i=1;i<=n;i++){Q[i-1].ID=i;Q[i-1].d=1.0*p[i]/w[i];P+=p[i];W+=w[i];}if(W<=c)returnP;//装入所有物品//依物品单位重量排序floatf;for(i=0;i

6、ntj=i;j

7、;//回溯搜索K.Backtrack(1);K.print();delete[]Q;delete[]K.w;delete[]K.p;returnK.bestp;}voidmain(){int*p;int*w;intc=0;intn=0;inti=0;cout<<"请输入背包个数："<>n;p=newint[n+1];w=newint[n+1];p[0]=0;w[0]=0;cout<<"请输入各背包的价值："<>p[i];cout<<"请

8、输入各背包的重量："<>w[i];cout<<"请输入背包容量："<>c;cout<