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

1、 / 7实验题目：用分支限界求解0-1 背包问题物品个数n=4,背包容量c=7,价值向量p=9, 10, 7,4,重量向量 w=3,5,2,1请求出最优的解及其目标函数值。#include #include#defineMaxSize 100/最多结点数typedefstructQNodefloatweight;floatvalue;intceng;structQNode *parent;bool leftChild;QNode,*qnode;/ 存放每个结点typedef structqnodeQMaxSize;int front,rear;SqQueue;存放结点的队列SqQueuesq;

2、float bestv=0; / 最优解int n=0;/ 实际物品数float wMaxSize;/ 物品的重量float vMaxSize;/ 物品的价值int bestxMaxSize;/ 存放最优解qnode bestE;void InitQueue(SqQueue &sq ) /队列初始化sq.front=1;sq.rear=1;bool QueueEmpty(SqQueue sq) /队列是否为空void EnQueue(SqQueue &sq,qnode b)队队qnode DeQueue(SqQueue &sq)/出队qnode e;if(sq.front=sq.rear)e=

3、sq.Qsq.front;printf( 队列已空 !);return 0;if(sq.front=(sq.rear+1)%MaxSize)sq.Qsq.rear=b;sq.rear=(sq.rear+1)%MaxSize;printf(队列已满！”)；return ;if(sq.front=sq.rear)return true;elsereturn false;sq.front=(sq.front+1)%MaxSize;return e;voidEnQueue1(float wt,float vt, int i ,QNode *parent, bool leftchild)voidmaxL

4、oading(float w,float v,int c)float wt=0;float vt=0;int i=1;/ 当前的扩展结点所在的层qnode b;if (i=n)/可行叶子结点b=(qnode)malloc(sizeof(QNode);非叶子结点b-weight=wt;b-value=vt;b-ceng=i;b-parent=parent;b-leftChild=leftchild;EnQueue(sq,b);if (vt=bestv)return;bestE=parent;bestxn=(leftchild)?1:0;float ew=0;/ 扩展节点所相应的当前载重量floa

5、t ev=0;/ 扩展结点所相应的价值qnode e=NULL;qnode t=NULL;InitQueue(sq);EnQueue(sq,t);空标志进队歹!Jwhile (!QueueEmpty(sq)printf( 最优取法为： n);wt=ew+wi;vt=ev+vi;if (wt bestv)bestv=vt;EnQueue1(wt,vt,i,e,true);/ 左儿子结点进队列EnQueue1(ew,ev,i,e,false);右儿子总是可行;e=DeQueue(sq);取下一扩展结点if (e = NULL)ew=e-weight;/ 更新当前扩展结点的值ev=e-value;i

6、f (QueueEmpty(sq)break;EnQueue(sq,NULL);/同层结点尾部标志e=DeQueue(sq);取下一扩展结点i+;for( int j=n-1;j0;j-)/ 构造最优解for(int k=1;kleftChild?1:0);bestE=bestE-parent;void main()int c;float ewvMaxSize;printf(510 专区 n);printf( 请输入物品的数量： n);scanf(%d,&n);printf( 请输入背包容量： n);scanf(%d,&c);printf(n 请输入物品价值和重量:nn);for(int i=1