实验报告 回溯法01背包

《实验报告 回溯法01背包》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》实验报告六学号：1004091130姓名：金玉琦日期：2011-11-17得分：一、实验内容：运用回溯法解决0-1背包问题二、所用算法的基本思想及复杂度分析：回溯法回溯法就是一种有组织的系统化搜索技术,可以看作是蛮力法穷举搜索的改进。回溯法每次只构造可能解的一部分,然后评估这个部分解,如果这个部分解有可能导致一个完整解,则对其进一步构造,否则,就不必继续构造这个部分解了。回溯法常常可以避免搜索所有的可能解。0-1背包问题1）基本思想给定n种物品和一个容量为C的背包,物品i的重量是Wi,其价值为Vi,0/

2、1背包问题是如何选择装入背包的物品(物品不可分割),使得装入背包中物品的总价值最大，设计可能解的表示方式,构成解空间树。2）复杂度分析时间复杂度是O(2n);三、源程序及注释：#includeusingnamespacestd;classKnap{friendintKnapsack(intp[],intw[],intc,intn);public:voidprint(){for(intm=1;m<=n;m++){cout<

3、und(inti);5voidBacktrack(inti);intc;//背包容量intn;//物品数int*w;//物品重量数组int*p;//物品价值数组intcw;//当前重量intcp;//当前价值intbestp;//当前最优值int*bestx;//当前最优解int*x;//当前解};intKnap::Bound(inti){//计算上界intcleft=c-cw;//剩余容量intb=cp;//以物品单位重量价值递减序装入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=

4、p[i];i++;}//装满背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;}voidKnap::Backtrack(inti){if(i>n){if(bestpbestp)//搜索右子树{x[

5、i]=0;Backtrack(i+1);}}classObject{friendintKnapsack(intp[],intw[],intc,intn);public:intoperator<=(Objecta)const{return(d>=a.d);}private:intID;floatd;};intKnapsack(intp[],intw[],intc,intn){//为Knap::Backtrack初始化intW=0;intP=0;inti=1;Object*Q=newObject[n];for(i=1;i<=

6、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)5returnP;//装入所有物品//依物品单位重量排序floatf;for(i=0;i

7、;K.x[0]=0;K.bestx[0]=0;for(i=1;i<=n;i++){K.p[i]=p[Q[i-1].ID];K.w[i]=w[Q[i-1].ID];}K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;//回溯搜索K.Backtrack(1);K.print();delete[]Q;delete[]K.w;delete[]K.p;returnK.bestp;}voidmain(){int*p;int*w;5intc=0;intn=0;inti=0;cout<<"请输入背包个数："<

8、dl;cin>>n;p=newint[n+1];w=newint[n+1];p[0]=0;w[0]=0;cout<<"请输入个背包的价值："<>p[i];cout<<"请输入个背包的重量："<>w[i];cou