回溯法解0-1背包问题实验报告

实验4回溯法解0-1背包问题一、实验要求1．要求用回溯法求解0-1背包问题；2．要求交互输入背包容量，物品重量数组，物品价值数组；3．要求显示结果。二、实验仪器和软件平台仪器：带usb接口微机软件平台：WIN-XP+VC++6.0三、实验源码#includestdafx.h#includeiostream#includecstdio#includeconio.h#includeiomanipusingnamespacestd;templateclasstyclassKnap{public:friendvoidInit();friendvoidKnapsack();friendvoidBacktrack(inti);friendfloatBound(inti);booloperator(Knaptya)const{if(fla.fl)returntrue;elsereturnfalse;}private:tyw;//重量tyv;//价值floatfl;//单位重量的价值v/wintkk;//记录第几个物品intflag;//记录是否放入包中};templateclasstyvoidSort(Knapty*li,intn){inti,j,k;Knaptyminl;for(i=1;in;i++){minl=li[0];k=0;for(j=1;j=n-i;j++){if(minlli[j]){minl=li[j];swap(li[j],li[k]);k=j;}}}}namespacejie//命名空间{intc=0,n=0;int*x=NULL;Knapint*bag=NULL;intcp=0,cw=0;intbestp=0;}usingnamespacejie;voidInit(){inti=0;coutendl;cout请输入物品数量n=;cinn;coutendl;cout请输入背包容量C=;cinc;coutendl;bag=newKnapint[n];x=newint[n];cout请依次输入n个物品的重量W:endl;for(i=0;in;i++)cinbag[i].w;coutendl;cout请依次输入n个物品的价值P:endl;for(i=0;in;i++)cinbag[i].v;for(i=0;in;i++){bag[i].flag=0;bag[i].kk=i;bag[i].fl=1.0*bag[i].v/bag[i].w;}}voidBacktrack(inti){if(i=n)//到达叶节点{bestp=cp;//更新最优价值return;}if(cw+bag[i].w=c)//进入左子树{bag[i].flag=1;cw+=bag[i].w;cp+=bag[i].v;Backtrack(i+1);cw-=bag[i].w;cp-=bag[i].v;}if(Bound(i+1)bestp)//进入右子树{bag[i].flag=0;Backtrack(i+1);}}//计算当前节点处的上界floatBound(inti){intcleft=c-cw;//剩余容量floatb=cp;while(in&&bag[i].w=cleft){//以物品单位重量价值递减序装入cleft-=bag[i].w;b+=bag[i].v;i++;}//装满背包if(in)b+=1.0*bag[i].v/bag[i].w*cleft;returnb;}voidKnapsack()//计算最优解和变量值{intL(0);//用L累计价值，初始价值设置为0for(intk=0;kn;k++){x[bag[k].kk]=bag[k].flag;//x=0表示未放入背包，x=1表示放入背包L+=bag[k].flag*bag[k].v;//价值累加}coutendl;cout当前最优价值为:Lendl;cout变量值x=;for(inti=1;i=n;i++){coutx[i-1];}delete[]bag;bag=NULL;delete[]x;x=NULL;coutendl;getch();}intmain(){coutendl;cout|**********回溯法解0-1背包问题**********|endl;Init();Backtrack(0);Knapsack();return0;}四、运行结果五、实验小结通过该实验，我充分了解了回溯法与分支界限法的区别。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。