01背包分支定界程序.doc

《01背包分支定界程序.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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;}/*用隊列實現(xiàn)分支定界算法*/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