01背包问题不同算法设计、分析与对比.docx

试验三Ol背包问题不同算法设计、分析与对比一 .问题描述给定n种物品和一背包。物品i的重量是叫，其价值为Vi,背包的容量为c。问题：应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。说明：在选择装入背包的物品时.，对每种物品i只有两个选择，装入背包或不装入背包，也不能将物品装入背包多次。二 .试验内容与要求试验内容：1.分析该问题适合采纳哪些算法求解(包括近似解)。动态规划、贪心、回溯和分支限界算法。2 .分别给出不同算法求解该问题的思想与算法设计，并进行算法困难性分析。动态规划：递推方程：m(i,j)=maxm(i-l,j),m(i-l,j-wi)+vij>=wi;m(i-l,j)j<wi;时间困难度为0(n).贪心法：算法思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。但是，贪心法当在只有在解决物品可以分割的背包问题时是正确的。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。用贪心法设计算法的特点是一步一步地进行，依据某个优化测度(可能是目标函数，也可能不是目标函数)，每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满意局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把全部数据枚举完，或者不能再添加为止。回溯法：回溯法：为了避开生成那些不行能产生最佳解的问题状态，要不断地利用限界函数(boundingfunction)来处死那些事实上不行能产生所需解的活结点，以削减问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成，可用子集数表示。在搜寻解空间树时，只要其左儿子结点是一个可行结点，搜寻就进入左子树。当右子树中有可能包含最优解时就进入右子树搜寻。时间困难度为：O(2rl)空间困难度为：0扁分支限界算法：首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。假如该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点肯定是可行结点，仅当右儿子结点满意上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。3 .设计并实现所设计的算法。4 .对比不同算法求解该问题的优劣。这动态规划算法和贪心算法是用来分别解决不同类型的背包问题的，当一件背包物品可以分割的时候，运用贪心算法，按物品的单位体积的价值排序，从大到小取即可。当一件背包物品不行分割的时候，(因为不行分割，所以就算按物品的单位体积的价值大的先取也不肯定是最优解)此时运用贪心是不对的，应运用动态规划。设计方法时间困难度优点缺点动态规划Minnc,2n可求得最优决策序列速度慢贪心方法0(2")速度较快很难得到最优解回溯法0(n2n)能够得到最优解时间困难度较高分支限界法O(2n)速度较快，易求解占用内存大，效率不高5 .须要提交不同算法的实现代码和总结报告。动态规划方法：publicclassKnapsackpublicstaticvoidmain(Stringargs)intvalue=0,60,100,120);intweigh=0,10,20,30);intweight=50;Knapsackl(weight,value,weigh);publicstaticvoidKnapsackl(intweight,intvalue,intweigh)(intv=newintvalue.length;intw=newintweigh.length;intc=newintvalue.lengthweight+1;intd=newint100;for(inti=0;i<value.length;i+)vi=valuei;wi=weighi;)for(inti=1;i<value.length;i+)for(intk=1;k<=weight;k+)if(wi<=k)cik=三x(ci-1k,ci-1k-wi+vi);elsec(ik=ci-1k;)System.out.printIn(c(value.length-1)weight);)privatestaticintmax(inti,intj)intk=i>j?i:j;returnk;)贪心法：publicclassGreedyKnapSackptblicstaticvoidmain(Stringargs)int(value=0,60,100,120);intweigh=0,10,20,30);intweight=50;Knapsackl(weight,value,weigh);)privatestaticvoidKnapsackl(intweight,intv,intw)intn=v.length;doubler=newdoublen;intindex=newintn;for(inti=0;i<n;i+)ri=(double)vi/(double)wi;indexi=i;/按单位重量价值ri=viwi降序排列doubletemp=0;for(inti=0;i<n-1;i+)for(intj=i+1;j<n;j+)if(ri<rj)temp=r(i;ri=rj;rj=temp;intx=indexi;indexi=indexj;indexj=x;)/排序后的重量和价值分别存到WI和Vi中intwl=newintn;intvl=newintn;for(inti=0;i<n;i+)wli=windex(i;vli=vindexi;)System,out.printin(Arrays.toString(vl);System.out.printIn(Arrays.toString(vl);intS=0;包内现存货品的重量intVaIUe=0"/包内现存货品总价值for(inti=0;i<n;i+)if(s+wli<weight)value+=vli;s+=wli;)value);System.out.printin("背包中物品的最大总价值为“)回溯法：publicclassBacktrackKnapSackpublicstaticvoidmain(Stringargs)intvalue=0,60,100,120);intweigh=0,10,20,30);intweight=50;Knapsackl(weight,value,weigh);privatestaticvoidKnapsackl(intweight,intv,intw)intn=v.length;doubler=newdoublen;int(index=newintn;for(inti=0;i<n;i+)ri=(double)vi/(double)wi;indexi=i;/按单位重量价值ri=viwi降序排列doubletemp=0;for(inti=0;i<n-1;i+)for(intj=i+1;j<n;j+)if(ri<rj)temp=ri;ri=rj;rj=temp;intx=indexi;indexi=indexj;indexj=x;)排序后的重量和价值分别存到WIn和VI中int(wl=newintn;intvl=newintn;for(inti=0;i<n;i+)wli=w(indexi;vli=vindexi;)调用函数KnapSackBackTrack(),输出打印装完物品以后的最大价值KnapSackBackTrack(wl,vl,wl.length,weight);)privatestaticvoidKnapSackBackTrack(intwlzintvl,intlength,intweight)intCurrentWeight=0;intCurrentValue=0;intmaxValue=0;inti=0;intn=vl.length;while(i>=0)if(Currentweight+wli<weight)CurrentWeight+=wli;CurrentValue+=vli;i+；)elsebreak;)if(i<n)maxValue=Currentvalue;SyStem.out.printin(”工背包中物品的最大总价值为"+maxValue);)分支限界算法：packagebaglb;importjava.util.Array1.ist;pxblicclassbag01dopublicstaticvoidmain(Stringargs)/TODOAuto-generatedmethodstubArray1.ist<object>objects=newArray1.isto();objects.add(newobject(10,60);objects.add(newobject(20,100);objects.add(newobject(30,120);bagb=newbag(50,objects);b.findmaxvalue();b.show();)packagebag01b;importjava.util.Array1.ist;importjava.util.Collections;importjava.util.PriorityQueue;publicclassbagprivateintbagv;privateArray1.ist<object>objects;privateintmaxvalue;privateArray1.ist<object>result_objects;publicbag(intv,Array1.ist<object>o)super();this.bagv=v;this.objects=o;this.maxvalue=0;this.result_objects=null;Collections.sort(objects);)publicvoidshow()System.out.println("maxvalue:"+this.maxvalue);System.out.println("theobjectwhenmaxvalue:"+this.result_objects);)publicvoidfindmaxvalue()PriorityQueue<Node>enode=newPriorityQueue<>();Nodenode=newNOde(0,null,bagv,this.objects);enode.offer(node);while(true)if(enode.isEmpty()break;node=enode.poll();if(node.isend()this.maxvalue=node.get_bag_value();this.result_objects=newArray1.isto(node.get_in_bag_object();return;)inti=node.get_node_in();objectiobject=this.objects.get(i);if(node.get_bag_weight()+iobject.getweight()<=this.bagv)Array1.ist<object>newnodeinbag=newArray1.ist<object>(node.get_in_bag_object();newnodeinbag.add(iobject);intnewnodebagv=node.get_bag_leftv()-iobject.getweight();Nodenewnode=newNode(i+l,newnodeinbagjnewnodebagv3his.objects);enode.add(newnode);if(newnode.get_bag_value()>this.maxvalue)this.maxvalue=newnode.get_bag_value();this,result_objects=newArray1.ist<>(newnode.get_in_bag_object();)Nodenewnode=newNode(i+l,nodeget_in_bag_object(),node.get_bag_leftv(),this.objects);if(newnode.get_bag_prio()>this.maxvalue)enode.add(newnode);)packagebag01b;importjava.util.Array1.ist;publicclassNodeimplementsComparable<Node>privateintnode_in;privateArray1.ist<object>inbag_object;privateArray1.ist<object>outbag_object;privateintleftv;privateintprio;publicNode(inti,Array1.ist<object>in,intljArray1.ist<object>out)super();this.node_in=i;if(in=null)in=newArray1.ist<>();this,inbag_object=in;this.Ieftv=I;this.outbag_object=out;this.prio=this.find_prio();)privateintfind_prio()/TODOAuto-generatedmethodstubintbag_left=this.leftv;intp=this.get_bag_value();inti=this.node_in;objectiobject=null;while(true)if(i>=this.inbag_object.size()break;iobject=this.inbag_object.get(i);if(iobject.getweight()>bag_left)break;bag_left-=iobject.getweight();p+=iobject.getvalue();i+;)if(i<=this.inbag_object.size()-l)p+=iobject.getvw()*bag_left;returnp;)publicintget_bag_weight()intw=0;for(objecto:this.inbag_object)w+=o.getweight();)returnw;)publicintget_bag_value()intw=0;for(objecto:this.inbag_object)w+=o.getvalue();)returnw;)0OverridepublicintcompareTo(Nodeo)/TODOAuto-generatedmethodstubif(this.prio>o.prio)return-1;if(this.prio<o.prio)return1;return0;)publicbooleanisend()if(this.node_in=this.outbag_object.size()returntrue;elsereturnfalse;)publicArray1.ist<object>get_in_bag_object()returnthis.inbag_object;)publicintget_node_in()returnthis.node_in;publicintget_bag_leftv()returnthis.leftv;publicintget_bag_prio()returnthis.prio;publicStringtoString()return"nodein,+this.node_in+"nodeprio,+this.prio;packagebag01b;publicclassobjectimplementsComparable<object>privatestaticintids=l;privateintid;privateintweihgt;privateintvalue;publicobject(intw,intv)super();this.weihgt=w;this.value=v;this.id=ids+;)publicintgetid()returnthis.id;publicintgetweight()returnthis.weihgt;publicintgetvalue()returnthis.value;publicfloatgetvw()return(float)this.value/this.weihgt;gOverridepublicintcompareTo(objecto)/TODOAuto-generatedmethodstubif(this.getvw()>o.getvw()return-1;if(this.getvw()<o.getvw()return1;return0;)publicStringtoString()return"object"+this.id+"”;