数据结构 分支界限法程序.doc

#include stdafx.h#include #include#include#include#define MaxSize 100 /最多结点数typedef struct aa int weight; int Value; int ceng; struct aa *parent; /Boolean leftChild; bool leftChild; QNode; /存放每个结点typedef struct QNode AMaxSize; int front,rear; SqQueue; /存放结点的队列SqQueue sq;int n; /实际物品数int bestxMaxSize; / 存放最优解int bestv;/ int EnQueue(QNode *b)if(sq.rear=MaxSize) return 0;/*sq.Asq.rear.weight=b.weightsq.Asq.rear.value=b.value;sq.Asq.rear.ceng=b.ceng;sq.Asq.rear.parent=b.parent;sq.Asq.rear.leftchild=b.leftchild;sq.rear=sq.rear+1;*/sq.Asq.rear=*b;sq.rear+;return 1; void EnQueue1(int wt,int vt, int i ,QNode *parent, bool leftchild) QNode *bestE=NULL,*b;if (i=n) /可行叶子结点 if (vt=bestv) bestE=parent; bestxn=(leftchild)?1:0; /*return*/ b= (QNode *)malloc(sizeof(QNode); /非叶子结点 b-parent=parent; b-leftChild=leftchild; b-weight=wt; b-Value=vt; EnQueue(b); int InitQueue(SqQueue Sq) int i;Sq.front=0; Sq.rear=0; for(i=0;iMaxSize;i+) Sq.Ai.weight=0; Sq.Ai.Value=0; Sq.Ai.ceng=0; Sq.Ai.parent=NULL; Sq.Ai.leftChild=false; / Sq.Ai=NULL; return 1;QNode *DeQueue(SqQueue &sq)QNode *e; if(sq.front!=sq.rear) e=&sq.Asq.front; sq.front+; return e;int QueueEmpty(SqQueue sq)if(sq.front=sq.rear)return 1;elsereturn 0; void main() int wt,vt,j,c,bestv=0; /SqQueue sq； int i=1; /当前的扩展结点所在的层 int ew=0; /扩展节点所相应的当前载重量 int ev=0; /扩展结点所相应的价值 QNode *e=NULL,*bestE=NULL; QNode *t=NULL;printf(物品的个数为：);scanf(%d,&n);int wMaxSize,vMaxSize;printf(物品的重量 价值:n); for(j=0;jn;j+)scanf(%d,&wj);scanf(%d,&vj);printf(n);printf(物品的限重为：);scanf(%d,&c); /Bestx=xx; InitQueue(sq); /printf(djfh); EnQueue1(0,0,0,t,0); /空标志进队列 while (true) 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(e); / 同层结点尾部标志 e=DeQueue(sq); / 取下一扩展结点 i+; ew=e-weight; /更新当前扩展结点的值 ev=e-Value; for( j=n-1;j0;j-) /构造最优解 bestxj=(bestE-leftChild?1:0); bestE=bestE-parent;/re