实验题目：用分支限界求解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{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(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->weight;//更新当前扩展结点的值ev=e->value;}printf("最优取法为：\n");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("\n物品%d:重量：%.1f，价值：%.1f\n",k,w[k],v[k]);}printf("\n");printf("最优价值为：%.1f\n\n",bestv);}voidmain(){intc;floatewv[MaxSize];printf("510专区\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",&ewv[i],&w[i]);v[i]=w[i]*ewv[i];printf("\n");}}实验结果：maxLoading(w,v,c);
VIP
