算法0-1背包問題教學教材

算法 0-1背包問題精品文檔一、實驗目的與要求掌握回溯法、分支限界法的原理，并能夠按其原理編程實現(xiàn)解決 0-1背包問題，以加深對回溯法、分支限界法的理解。1．要求分別用回溯法和分支限界法求解 0-1背包問題；2．要求交互輸入背包容量，物品重量數(shù)組，物品價值數(shù)組；3．要求顯示結果。二、實驗方案在選擇裝入背包的物品時，對每種物品 i只有2種選擇，即裝入背包或不裝入背包。不能將物品 i裝入背包多次，也不能只裝入部分的物品 i。三、實驗結果和數(shù)據(jù)處理1．用回溯法解決0-1背包問題：代碼：importjava.util.*;publicclassKnapsack{privatedouble[]p,w;//分別代表價值和重量privateintn;privatedoublec,bestp,cp,cw;privateintx[];//記錄可選的物品privateint[]cx;publicKnapsack(doublepp[],doubleww[],doublecc){this.p=pp;this.w=ww;this.n=pp.length-1;this.c=cc;this.cp=0;this.cw=0;this.bestp=0;x=newint[ww.length];cx=newint[pp.length];}voidKnapsack(){backtrack(0);收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔}voidbacktrack(inti){if(i>n){ //判斷是否到達了葉子節(jié)點if(cp>bestp){for(intj=0;j<x.length;j++)x[j]=cx[j];bestp=cp;}return;}if(cw+w[i]<=c){//搜索右子樹cx[i]=1;cw+=w[i];cp+=p[i];backtrack(i+1);cw-=w[i];cp-=p[i];}cx[i]=0;backtrack(i+1);//檢查左子樹}voidprintResult(){System.out.println("回溯法");System.out.println("物品個數(shù)：n=4");System.out.println("背包容量：c=7");System.out.println("物品重量數(shù)組：w={3,5,2,1}");System.out.println("物品價值數(shù)組：p={9,10,7,4}");System.out.println("最優(yōu)值：="+bestp);System.out.println("選中的物品是:");for(inti=0;i<x.length;i++){收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔System.out.print(x[i]+"");}}publicstaticvoidmain(String[]args){doublep[]={9,10,7,4};doublew[]={3,5,2,1};intmaxweight=7;Knapsackks=newKnapsack(p,w,maxweight);ks.Knapsack(); //回溯搜索ks.printResult();}}運行結果：2．用優(yōu)先隊列式分支限界法解決 0-1背包問題：代碼：publicclassKnapsack{staticdoublec;收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔staticintn;staticdoublew[];staticdoublep[];staticdoublecw;staticdoublecp;staticintbestX[];staticMaxHeapheap;//上界函數(shù)bound計算結點所相應價值的上界privatestaticdoublebound(inti){doublecleft=c-cw;doubleb=cp;while(i<=n&&w[i]<=cleft){cleft=cleft-w[i];b=b+p[i];i++;}//裝填剩余容量裝滿背包if(i<=n)b=b+p[i]/w[i]*cleft;returnb;}//addLiveNode將一個新的活結點插入到子集樹和優(yōu)先隊列中privatestaticvoidaddLiveNode(doubleup,doublepp,doubleww,intlev,BBnodepar,booleanch){//將一個新的活結點插入到子集樹和最大堆中BBnodeb=newBBnode(par,ch);HeapNodenode=newHeapNode(b,up,pp,ww,lev);heap.put(node);}privatestaticdoubleMaxKnapsack(){//優(yōu)先隊列式分支限界法，返回最大價值， bestx返回最優(yōu)解BBnodeenode=null;inti=1;doublebestp=0;//當前最優(yōu)值doubleup=bound(1);//當前上界收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔while(i!=n+1){//非葉子結點//檢查當前擴展結點的左兒子子結點doublewt=cw+w[i];if(wt<=c){if(cp+p[i]>bestp)bestp=cp+p[i];addLiveNode(up,cp+p[i],cw+w[i],i+1,enode,true);}up=bound(i+1);if(up>=bestp)addLiveNode(up,cp,cw,i+1,enode,false);HeapNodenode=(HeapNode)heap.removeMax();enode=node.liveNode;cw=node.weight;cp=fit;up=node.upperProfit;i=node.level;}for(intj=n;j>0;j--){bestX[j]=(enode.leftChild)?1:0;enode=enode.parent;}returncp;}publicstaticdoubleKnapsack(doublepp[],doubleww[],doublecc,intxx[]){//返回最大值，bestX返回最優(yōu)解c=cc;n=pp.length-1;//定義以單位重量價值排序的物品數(shù)組Elementq[]=newElement[n];doublews=0.0;doubleps=0.0;for(inti=0;i<n;i++){q[i]=newElement(i+1,pp[i+1]/ww[i+1]);ps=ps+pp[i+1];ws=ws+ww[i+1];}if(ws<=c)收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔{returnps;}p=newdouble[n+1];w=newdouble[n+1];for(inti=0;i<n;i++){p[i+1]=pp[q[i].id];w[i+1]=ww[q[i].id];}cw=0.0;cp=0.0;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);System.out.println("優(yōu)先隊列式分支限界法 :");System.out.println("物品個數(shù)：n=4");System.out.println("背包容量：c=7");System.out.println("物品重量數(shù)組：w={3,5,2,1}");System.out.println("物品價值數(shù)組：p={9,10,7,4}");System.out.println("最優(yōu)值：="+m);System.out.println("選中的物品是:");for(inti=1;i<=4;i++)System.out.print(x[i]+"");收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔}}//子空間中節(jié)點類型classBBnode{BBnodeparent;//父節(jié)點booleanleftChild;//左兒子節(jié)點標志BBnode(BBnodepar,booleanch){parent=par;leftChild=ch;}}classHeapNodeimplementsComparable{BBnodeliveNode;//活結點doubleupperProfit;//結點的價值上界doubleprofit;//結點所相應的價值doubleweight;//結點所相應的重量intlevel;//活結點在子集樹中所處的層次號//構造方法publicHeapNode(BBnodenode,doubleup,doublepp,doubleww,intlev){liveNode=node;upperProfit=up;profit=pp;weight=ww;level=lev;}publicintcompareTo(Objecto){doublexup=((HeapNode)o).upperProfit;收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔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)Math.pow((double)2,(double)n);nextPlace=1;//下一個存放位置nodes=newHeapNode[maxNumber];}publicstaticvoidput(HeapNodenode){nodes[nextPlace]=node;nextPlace++;收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔heapSort(nodes);}publicstaticHeapNoderemoveMax(){HeapNodetempNode=nodes[1];nextPlace--;nodes[1]=nodes[nextPlace];heapSort(nodes);returntempNode;}privatestaticvoidheapAdjust(HeapNode[]nodes,ints,intm){HeapNoderc=nodes[s];for(intj=2*s;j<=m;j*=2){if(j<m&&nodes[j].upperProfit<nodes[j+1].upperProfit)++j;if(!(rc.upperProfit<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);}}}運行結果：收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔3．用隊列式分支限界法解決 0-1背包問題：代碼：#include<stdio.h>#include<stdlib.h>#defineMAXNUM 100structnode{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");收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔elsepaqu->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");elsepaqu->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++)收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔{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++;收集于網(wǎng)絡，如有侵權請聯(lián)系管理員刪除精品文檔}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);if(min==0)return-1;enQueue_seq(q,x);while(!isEmptyQueue_seq(q)){intstep;DataTypey;x=frontQueue_seq(q);deQueue_seq(q);if(x.max<min)continue;step=x.step+1;if(step==n+1)continue;y.max=x.price+up(step,m-x.weight,n,p,w);if(y.max>=min){y.min=x.price+down(step,m-x.weight,n,p,w);y.price=x.price;y.weight=x.weight;y.step=step;