算法 0-1背包問題

算法0-1背包問題算法0-1背包問題算法0-1背包問題算法0-1背包問題編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:一、實驗?zāi)康呐c要求掌握回溯法、分支限界法的原理，并能夠按其原理編程實現(xiàn)解決0-1背包問題，以加深對回溯法、分支限界法的理解。要求分別用回溯法和分支限界法求解0-1背包問題；要求交互輸入背包容量，物品重量數(shù)組，物品價值數(shù)組；要求顯示結(jié)果。二、實驗方案在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。三、實驗結(jié)果和數(shù)據(jù)處理1．用回溯法解決0-1背包問題：代碼：import.*;publicclassKnapsack{privatedouble[]p,w;d];w[i+1]=ww[q[i].id];}cw=;cp=;bestX=newint[n+1];heap=newMaxHeap(n);doublebestp=MaxKnapsack();for(intj=0;j<n;j++)xx[q[j].id]=bestX[j+1];returnbestp;}publicstaticvoidmain(String[]args){doublew[]=newdouble[5];w[1]=3;w[2]=5;w[3]=2;w[4]=1;doublep[]=newdouble[5];p[1]=9;p[2]=10;p[3]=7;p[4]=4;doublec=7;intx[]=newint[5];doublem=Knapsack(p,w,c,x);"優(yōu)先隊列式分支限界法:");"物品個數(shù)：n=4");"背包容量：c=7");"物品重量數(shù)組：w={3,5,2,1}");"物品價值數(shù)組：p={9,10,7,4}");"最優(yōu)值：="+m);"選中的物品是:");for(inti=1;i<=4;i++)"");}}pperProfit;if(upperProfit<xup)return-1;if(upperProfit==xup)return0;elsereturn1;}}classElementimplementsComparable{intid;doubled;publicElement(intidd,doubledd){id=idd;d=dd;}publicintcompareTo(Objectx){doublexd=((Element)x).d;if(d<xd)return-1;if(d==xd)return0;return1;}publicbooleanequals(Objectx){returnd==((Element)x).d;}}classMaxHeap{staticHeapNode[]nodes;staticintnextPlace;staticintmaxNumber;publicMaxHeap(intn){maxNumber=(int)((double)2,(double)n);nextPlace=1;pperProfit<nodes[j+1].upperProfit)++j;if(!<nodes[j].upperProfit))break;nodes[s]=nodes[j];s=j;}nodes[s]=rc;}privatestaticvoidheapSort(HeapNode[]nodes){for(inti=(nextPlace-1)/2;i>0;--i){heapAdjust(nodes,i,nextPlace-1);}}}運行結(jié)果：3．用隊列式分支限界法解決0-1背包問題：代碼：#include<>#include<>#defineMAXNUM100structnode{ intstep; doubleprice;doubleweight;doublemax,min;unsignedlongpo;};typedefstructnodeDataType;structSeqQueue{/*順序隊列類型定義*/ intf,r; DataTypeq[MAXNUM];};typedefstructSeqQueue*PSeqQueue;PSeqQueuecreateEmptyQueue_seq(void){ PSeqQueuepaqu; paqu=(PSeqQueue)malloc(sizeof(structSeqQueue)); if(paqu==NULL) printf("Outofspace!!\n"); else paqu->f=paqu->r=0; returnpaqu;}intisEmptyQueue_seq(PSeqQueuepaqu){ returnpaqu->f==paqu->r;}/*在隊列中插入一元素x*/voidenQueue_seq(PSeqQueuepaqu,DataTypex){if((paqu->r+1)%MAXNUM==paqu->f) printf("Fullqueue.\n"); else { paqu->q[paqu->r]=x;paqu->r=(paqu->r+1)%MAXNUM; }}/*刪除隊列頭元素*/voiddeQueue_seq(PSeqQueuepaqu){ if(paqu->f==paqu->r) printf("EmptyQueue.\n"); 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<n-1;i++) for(j=i;j<n-1;j++) { doublea=p[j]/w[j]; doubleb=p[j+1]/w[j+1]; if(a<b) { doubletemp=p[j];p[j]=p[j+1];p[j+1]=temp;temp=w[j];w[j]=w[j+1];w[j+1]=temp;}}}/*求最大可能值*/doubleup(intk,doublem,intn,doublep[],doublew[]){ inti=k;doubles=0;while(i<n&&w[i]<m) { m-=w[i];s+=p[i];i++;}if(i<n&&m>0) { s+=p[i]*m/w[i];i++;} returns;}/*求最小可能值*/doubledown(intk,doublem,intn,doublep[],doublew[]){inti=k;doubles=0;while(i<n&&w[i]<=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);=up(0,m,n,p,w);=min=down(0,m,n,p,w);if(min==0)return-1;enQueue_seq(q,x);while(!isEmptyQueue_seq(q)) { intstep;DataTypey;x=frontQueue_seq(q);deQueue_seq(q); if<min)continue;step=+1;if(step==n+1)continue;=+up(step,m-,n,p,w);if>=min) { =+down(step,,n,p,w);=;=;=step;=<<1;if>=min) { min=;if(step==n)*po=;}enQueue_seq(q,y);}if+w[step-1]<=m) { =+p[step-1]+ up(step,[step-1],n,p,w);if>=min){=+p[step-1]+ down(step,[step-1],n,p,w);=+p[step-1];=+w[step-1];=step;=<<1)+1;if>=min) { min=;if(step==n)*po=;}enQueue_seq(q,y); } } } returnmin;}#definen4doublem=7;doublep[n]={9,10,7,4};doublew[n]={3,5,1,2};in