算法 0-1背包问题

算法0-1背包问题算法0-1背包问题算法0-1背包问题算法0-1背包问题编制仅供参考审核批准生效日期地址：电话：传真:邮编:一、实验目的与要求掌握回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对回溯法、分支限界法的理解。要求分别用回溯法和分支限界法求解0-1背包问题；要求交互输入背包容量，物品重量数组，物品价值数组；要求显示结果。二、实验方案在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。三、实验结果和数据处理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);"优先队列式分支限界法:");"物品个数：n=4");"背包容量：c=7");"物品重量数组：w={3,5,2,1}");"物品价值数组：p={9,10,7,4}");"最优值：="+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);}}}运行结果：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;}/*用队列实现分支定界算法*/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