资源描述:
《用分支限界求解0-1背包问题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、实验题目:用分支限界求解0-1背包问题物品个数n=4,背包容量c=7,价值向量p={9,10,7,4},重量向量w={3,5,2,1}请求出最优的解及其目标函数值。#include#include#defineMaxSize100//最多结点数typedefstructQNode{floatweight;floatvalue;intceng;structQNode*parent;boolleftChild;}QNode,*qnode;//存放每个结点typedefstruct{qno
2、deQ[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
3、.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
4、;}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->valu
5、e=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(!
6、QueueEmpty(sq)){wt=ew+w[i];vt=ev+v[i];if(wt<=c){if(vt>bestv)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->we
7、ight;//更新当前扩展结点的值ev=e->value;}printf("最优取法为:");for(intj=n-1;j>0;j--)//构造最优解{bestx[j]=(bestE->leftChild?1:0);bestE=bestE->parent;}for(intk=1;k<=n;k++){if(bestx[k]==1)printf("物品%d:重量:%.1f,价值:%.1f",k,w[k],v[k]);}printf("");printf("最优价值为:%.1f",bestv);}voi
8、dmain(){intc;floatewv[MaxSize];printf("510专区");printf("请输入物品的数量:");scanf("%d",&n);printf("请输入背包容量:");scanf("%d",&c);printf("请输入物品价值和重量:");for(inti=