算法0-1背包问题教学教材

算法 0-1背包问题精品文档一、实验目的与要求掌握回溯法、分支限界法的原理，并能够按其原理编程实现解决 0-1背包问题，以加深对回溯法、分支限界法的理解。1．要求分别用回溯法和分支限界法求解 0-1背包问题；2．要求交互输入背包容量，物品重量数组，物品价值数组；3．要求显示结果。二、实验方案在选择装入背包的物品时，对每种物品 i只有2种选择，即装入背包或不装入背包。不能将物品 i装入背包多次，也不能只装入部分的物品 i。三、实验结果和数据处理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);收集于网络，如有侵权请联系管理员删除精品文档}voidbacktrack(inti){if(i>n){ //判断是否到达了叶子节点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("物品个数：n=4");System.out.println("背包容量：c=7");System.out.println("物品重量数组：w={3,5,2,1}");System.out.println("物品价值数组：p={9,10,7,4}");System.out.println("最优值：="+bestp);System.out.println("选中的物品是:");for(inti=0;i<x.length;i++){收集于网络，如有侵权请联系管理员删除精品文档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．用优先队列式分支限界法解决 0-1背包问题：代码：publicclassKnapsack{staticdoublec;收集于网络，如有侵权请联系管理员删除精品文档staticintn;staticdoublew[];staticdoublep[];staticdoublecw;staticdoublecp;staticintbestX[];staticMaxHeapheap;//上界函数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将一个新的活结点插入到子集树和优先队列中privatestaticvoidaddLiveNode(doubleup,doublepp,doubleww,intlev,BBnodepar,booleanch){//将一个新的活结点插入到子集树和最大堆中BBnodeb=newBBnode(par,ch);HeapNodenode=newHeapNode(b,up,pp,ww,lev);heap.put(node);}privatestaticdoubleMaxKnapsack(){//优先队列式分支限界法，返回最大价值， bestx返回最优解BBnodeenode=null;inti=1;doublebestp=0;//当前最优值doubleup=bound(1);//当前上界收集于网络，如有侵权请联系管理员删除精品文档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返回最优解c=cc;n=pp.length-1;//定义以单位重量价值排序的物品数组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)收集于网络，如有侵权请联系管理员删除精品文档{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("优先队列式分支限界法 :");System.out.println("物品个数：n=4");System.out.println("背包容量：c=7");System.out.println("物品重量数组：w={3,5,2,1}");System.out.println("物品价值数组：p={9,10,7,4}");System.out.println("最优值：="+m);System.out.println("选中的物品是:");for(inti=1;i<=4;i++)System.out.print(x[i]+"");收集于网络，如有侵权请联系管理员删除精品文档}}//子空间中节点类型classBBnode{BBnodeparent;//父节点booleanleftChild;//左儿子节点标志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;收集于网络，如有侵权请联系管理员删除精品文档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++;收集于网络，如有侵权请联系管理员删除精品文档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);}}}运行结果：收集于网络，如有侵权请联系管理员删除精品文档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");收集于网络，如有侵权请联系管理员删除精品文档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++)收集于网络，如有侵权请联系管理员删除精品文档{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;}/*用队列实现分支定界算法 */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;