01背包分支定界程序.doc

《01背包分支定界程序.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、0/1背包问题的分支定界法算法0/1背包问题的分支定界法算法2009-09-1418:10/*0/1背包问题的分支定界法算法*/#include#include#defineMAXNUM  100structnode{   intstep;   doubleprice;   doubleweight;   doublemax,min;   unsignedlongpo;};typedefstructnodeDataType;structSeqQueue{       /*顺序队列类型定义*/   intf,r;   Dat

2、aTypeq[MAXNUM];};typedefstructSeqQueue*PSeqQueue;   PSeqQueuecreateEmptyQueue_seq(void){   PSeqQueuepaqu;   paqu=(PSeqQueue)malloc(sizeof(structSeqQueue));   if(paqu==NULL)       printf("Outofspace!!");   else       paqu->f=paqu->r=0;   returnpaqu;}intisEmptyQueue_seq(PSeqQueuepaq

3、u){   returnpaqu->f==paqu->r;}/*在队列中插入一元素x*/voidenQueue_seq(PSeqQueuepaqu,DataTypex){   if((paqu->r+1)%MAXNUM==paqu->f)       printf("Fullqueue.");   else{       paqu->q[paqu->r]=x;       paqu->r=(paqu->r+1)%MAXNUM;   }}/*删除队列头元素*/voiddeQueue_seq(PSeqQueuepaqu){   if(paqu->f==paqu

4、->r)       printf("EmptyQueue.");   else       paqu->f=(paqu->f+1)%MAXNUM;}/*对非空队列,求队列头部元素*/DataTypefrontQueue_seq(PSeqQueuepaqu){   return(paqu->q[paqu->f]);}/*物品按性价比从新排序*/voidsort(intn,doublep[],doublew[]){   inti,j;   for(i=0;i

5、ea=p[j]/w[j];           doubleb=p[j+1]/w[j+1];           if(a

6、ntn,doublep[],doublew[]){   inti=k;   doubles=0;   while(i0){       s+=p[i]*m/w[i];       i++;   }   returns;}/*求最小可能值*/doubledown(intk,doublem,intn,doublep[],doublew[]){   inti=k;   doubles=0;   while(i

7、m){       m-=w[i];       s+=p[i];       i++;   }   returns;}/*用队列实现分支定界算法*/doublesolve(doublem,intn,doublep[],doublew[],unsignedlong*po){   doublemin;   PSeqQueueq=createEmptyQueue_seq();   DataTypex={0,0,0,0,0,0};   sort(n,p,w);   x.max=up(0,m,n,p,w);   x.min=min=down(0,m,n,p,w);  

8、 if(min==0)return-1