用分支限界求解0-1背包问题

用分支限界求解0-1背包问题

ID:33717628

大小:52.50 KB

页数:6页

时间:2019-02-28

用分支限界求解0-1背包问题_第1页
用分支限界求解0-1背包问题_第2页
用分支限界求解0-1背包问题_第3页
用分支限界求解0-1背包问题_第4页
用分支限界求解0-1背包问题_第5页
资源描述:

《用分支限界求解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=

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。