背包问题实验报告

背包问题实验报告一、实验题目的：分别用贪心法和分支限界法求解背包问题和0-1背包问题二、实验内容：0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?三、在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。贪心法：程序源代码：#includeiostream#includevector#includealgorithmusingnamespacestd;structMouse{doubleJ;doubleF;doublea;};boolComp(constMouse&d1,constMouse&d2){if(d1.a!=d2.a)returnd1.ad2.a;elsereturnd1.Fd2.F;}intmain(){vectorMousev;Mousemouse;intm,n,i;cout.precision(3);doublesum;cout贪心算法:endl;cout请输入背包的容量及物品的件数endl;while(cinmn){if(m==-1&&n==-1)break;v.clear();sum=0.0;for(i=1;in+1;i++){cout请输入第i件物品的价值及重量endl;cinmouse.Jmouse.F;mouse.a=mouse.J/mouse.F;v.push_back(mouse);}sort(v.begin(),v.end(),Comp);for(intj=0;jv.size();j++){if(m=v[j].F){sum=sum+v[j].J;m=m-v[j].F;}else{sum=sum+m*v[j].a;}}coutfixedsumendl;}return0;}分支界限法：#includestdio.h#includemalloc.h#defineMaxSize100//最多结点数typedefstructQNode{floatweight;floatvalue;intceng;structQNode*parent;boolleftChild;}QNode,*qnode;//存放每个结点typedefstruct{qnodeQ[MaxSize];intfront,rear;}SqQueue;//存放结点的队列SqQueuesq;floatbestv=0;//最优解intn=0;//实际物品数floatw[MaxSize];//物品的重量floatv[MaxSize];//物品的价值intbestx[MaxSize];//存放最优解qnodebestE;voidInitQueue(SqQueue&sq)//队列初始化{sq.front=1;sq.rear=1;}boolQueueEmpty(SqQueuesq)//队列是否为空{if(sq.front==sq.rear)returntrue;elsereturnfalse;}voidEnQueue(SqQueue&sq,qnodeb)//入队{if(sq.front==(sq.rear+1)%MaxSize){printf(队列已满!);return;}sq.Q[sq.rear]=b;sq.rear=(sq.rear+1)%MaxSize;}qnodeDeQueue(SqQueue&sq)//出队{qnodee;if(sq.front==sq.rear){printf(队列已空!);return0;}e=sq.Q[sq.front];sq.front=(sq.front+1)%MaxSize;returne;}voidEnQueue1(floatwt,floatvt,inti,QNode*parent,boolleftchild){qnodeb;if(i==n)//可行叶子结点{if(vt==bestv){bestE=parent;bestx[n]=(leftchild)?1:0;}return;}b=(qnode)malloc(sizeof(QNode));//非叶子结点b-weight=wt;b-value=vt;b-ceng=i;b-parent=parent;b-leftChild=leftchild;EnQueue(sq,b);}voidmaxLoading(floatw[],floatv[],intc){floatwt=0;floatvt=0;inti=1;//当前的扩展结点所在的层floatew=0;//扩展节点所相应的当前载重量floatev=0;//扩展结点所相应的价值qnodee=NULL;qnodet=NULL;InitQueue(sq);EnQueue(sq,t);//空标志进队列while(!QueueEmpty(sq)){wt=ew+w[i];vt=ev+v[i];if(wt=c){if(vtbestv)bestv=vt;EnQueue1(wt,vt,i,e,true);//左儿子结点进队列}EnQueue1(ew,ev,i,e,false);//右儿子总是可行；e=DeQueue(sq);//取下一扩展结点if(e==NULL){if(QueueEmpty(sq))break;EnQueue(sq,NULL);//同层结点尾部标志e=DeQueue(sq);//取下一扩展结点i++;}ew=e-weight;//更新当前扩展结点的值ev=e-value;}printf(最优取法为：\n);for(intj=n-1;j0;j--)//构造最优解{bestx[j]=(bestE-leftChild?1:0);bestE=bestE-parent;}for(intk=1;k=n;k++){if(bestx[k]==1)printf(\n物品%d:重量：%.1f，价值：%.1f\n,k,w[k],v[k]);}printf(\n);printf(最优价值为：%.1f\n\n,bestv);}voidmain(){intc;floatewv[MaxSize];printf(////////////////////0-1背包问题分枝限界法/////////////////////\n\n);printf(请输入物品的数量：\n);scanf(%d,&n);printf(请输入背包的最大承重量：\n);scanf(%d,&c);printf(\n请输入物品的重量和单位重量价值:\n\n);for(inti=1;i=n;i++){printf(物品%d:,i);scanf(%f%f,&w[i],&ewv[i]);v[i]=w[i]*ewv[i];printf(\n);}maxLoading(w,v,c);}