1、实验题目：用分支限界求解 0-1 背包问题物品个数 n=4，背包容量 c=7，价值向量 p=9 ，10，7,4 ，重量向量w=3,5,2,1请求出最优的解及其目标函数值。#include #include#define MaxSize 100 /最多结点数typedef struct QNode float weight;float value;int ceng;struct QNode *parent;bool leftChild;QNode,*qnode; /存放每个结点typedef struct qnode QMaxSize; int front,rear;SqQueue; /存放结点
2、的队列SqQueue sq;float bestv=0; /最优解int n=0; /实际物品数float wMaxSize; /物品的重量float vMaxSize; /物品的价值int bestxMaxSize; / 存放最优解qnode bestE;void InitQueue(SqQueue sq.rear=1;bool QueueEmpty(SqQueue sq) /队列是否为空if(sq.front=sq.rear)return true;else return false;void EnQueue(SqQueue return ;sq.Qsq.rear=b;sq.rear=(s
3、q.rear+1)%MaxSize;qnode DeQueue(SqQueue if(sq.front=sq.rear)printf(“队列已空!“);return 0;e=sq.Qsq.front;sq.front=(sq.front+1)%MaxSize;return e;void EnQueue1(float wt,float vt, int i ,QNode *parent, bool leftchild)qnode b;if (i=n) /可行叶子结点if (vt=bestv)bestE=parent;bestxn=(leftchild)?1:0;return;b=(qnode)ma
4、lloc(sizeof(QNode); /非叶子结点b-weight=wt;b-value=vt;b-ceng=i;b-parent=parent; b-leftChild=leftchild; EnQueue(sq,b); void maxLoading(float w,float v,int c) float wt=0;float vt=0;int i=1; /当前的扩展结点所在的层float ew=0; /扩展节点所相应的当前载重量float ev=0; /扩展结点所相应的价值qnode e=NULL;qnode t=NULL;InitQueue(sq);EnQueue(sq,t); /
5、空标志进队列while (!QueueEmpty(sq) 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)if (QueueEmpty(sq) break;EnQueue(sq,NULL); / 同层结点尾部标志e=DeQueue(sq); / 取下一扩展结点i+;ew=e-weight; /更新当前扩展结点的值ev=e-value;prin
6、tf(“最优取法为：n“);for( int j=n-1;j0;j-) /构造最优解bestxj=(bestE-leftChild?1:0);bestE=bestE-parent;for(int k=1;k=n;k+)if(bestxk=1)printf(“n 物品%d: 重量：%.1f，价值：%.1fn“,k,wk,vk);printf(“n“);printf(“最优价值为：%.1fnn“,bestv);void main()int c;float ewvMaxSize;printf(“510 专区n“);printf(“请输入物品的数量：n“);scanf(“%d“,printf(“请输入背包容量：n“);scanf(“%d“,printf(“n 请输入物品价值和重量:nn“);for(int i=1;i=n;i+)printf(“物品%d:“,i);scanf(“%f%f“,vi=wi*ewvi;printf(“n“);实验结果： maxLoading(w, v, c);
