0-1背包问题(分支限界法)

1、-可编辑修改-分支限界法01背包问题12软工028胡梦颖问题描述0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。问题分析分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数

2、值达到极大或极小的解，即在某种意义下的最优解。由于求解目标不同，导致分支限界法与回溯法对解空间的搜索方式也不相同。回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。分支限界法的搜索策略是，在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。这种方式称为分支限界法。人们已经用分支限界法解决了大量离散最优化的问

3、题。三源代码#include#include/结点数的最大值#defineMaxSize100/结点数的最大值typedefstructQNodefloatweight;floatvalue;intceng;structQNode*parent;boolleftChild;QNode,*qnode;typedefstructqnodeQMaxSize;intfront,rear;/存放结点的队列/最优解/存放结点的队列/最优解/实际物品数SqQueuesq;floatbestv=0;intn=0;floatwMaxSize;/物品的floatwMaxSize;/物品的重量floatvMaxSi

4、ze;/物品的价值intbestxMaxSize;/存放最优解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.Qsq.rear=b;sq.rear=(sq.rear+1)%MaxSiz

5、e;qnodeDeQueue(SqQueue&sq)/出队qnodee;if(sq.front=sq.rear)printf(队列已空!)return0;e=sq.Qsq.front;sq.front=(sq.front+1)%MaxSize;returne;voidEnQueue1(floatwt,floatvt,inti,QNode*parent,boolleftchild)qnodeb;if(i=n)/可行叶子结点if(vt=bestv)bestE=parent;bestxn=(leftchild)?1:0;return;b=(qnode)malloc(sizeof(QNode);/非叶

6、子结点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+wi;vt=ev+

7、vi;if(wtbestv)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-)/构造最优解bestxj=(bestE-leftChild?1:0);bestE=bestE-parent;for(intk=1;k=n;k+)if(bestxk=1)printf(物品：重量：.1f，价值：%.1fn,k,wk,vk);printf(最大价值为：.1fn,bestv);voidmain()intc;floatewvMaxSize;printf(请输入背包的最大容量v:);scanf(%d,&c);printf(请输入物品总数n：)；scanf(%d