关闭

关闭

关闭

封号提示

内容

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

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

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

安静的夜晚_谁能不孤单
2019-01-11 0人阅读 0 0 0 暂无简介 举报

简介:本文档为《01背包问题不同算法设计、分析与对比doc》,可适用于工程科技领域

实验三背包问题不同算法设计、分析与对比一.问题描述给定n种物品和一背包。物品i的重量是wi其价值为vi背包的容量为c。问题:应如何选择装入背包中的物品使得装入背包中物品的总价值最大。说明:在选择装入背包的物品时对每种物品i只有两个选择装入背包或不装入背包也不能将物品装入背包多次。二.实验内容与要求实验内容:分析该问题适合采用哪些算法求解(包括近似解)。动态规划、贪心、回溯和分支限界算法。分别给出不同算法求解该问题的思想与算法设计并进行算法复杂性分析。动态规划:递推方程:m(i,j)=max{m(i,j),m(i,jwi)vi}j>=wim(i,j)j<wi时间复杂度为O(n)贪心法:算法思想:贪心原则为单位价值最大且重量最小不超过背包最大承重量为约束条件。也就是说存在单位重量价值相等的两个包则选取重量较小的那个背包。但是贪心法当在只有在解决物品可以分割的背包问题时是正确的。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑它所作出的选择只是在某种意义上的局部最优选择。用贪心法设计算法的特点是一步一步地进行根据某个优化测度(可能是目标函数也可能不是目标函数)每一步上都要保证能获得局部最优解。每一步只考虑一个数据它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时就不把该数据添加到部分解中直到把所有数据枚举完或者不能再添加为止。回溯法:回溯法:为了避免生成那些不可能产生最佳解的问题状态要不断地利用限界函数(boundingfunction)来处死那些实际上不可能产生所需解的活结点以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。对于有n种可选物品的背包问题其解空间由长度为n的向量组成,可用子集数表示。在搜索解空间树时只要其左儿子结点是一个可行结点搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。时间复杂度为:O(n)空间复杂度为:O(n)分支限界算法:首先要对输入数据进行预处理将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。设计并实现所设计的算法。对比不同算法求解该问题的优劣。这动态规划算法和贪心算法是用来分别解决不同类型的背包问题的当一件背包物品可以分割的时候使用贪心算法按物品的单位体积的价值排序从大到小取即可。当一件背包物品不可分割的时候(因为不可分割所以就算按物品的单位体积的价值大的先取也不一定是最优解)此时使用贪心是不对的应使用动态规划。设计方法时间复杂度优点缺点动态规划Min{ncn}可求得最优决策序列速度慢贪心方法O(n)速度较快很难得到最优解回溯法O(nn)能够得到最优解时间复杂度较高分支限界法O(n)速度较快易求解占用内存大效率不高    需要提交不同算法的实现代码和总结报告。动态规划方法:publicclassKnapsack{publicstaticvoidmain(Stringargs){intvalue={,,,}intweigh={,,,}intweight=Knapsack(weight,value,weigh)}publicstaticvoidKnapsack(intweight,intvalue,intweigh){intv=newintvaluelengthintw=newintweighlengthintc=newintvaluelengthweightintd=newintfor(inti=i<valuelengthi){vi=valueiwi=weighi}for(inti=i<valuelengthi){for(intk=k<=weightk){if(wi<=k){cik=max(cik,cikwivi)}else{cik=cik}}}Systemoutprintln(cvaluelengthweight)}privatestaticintmax(inti,intj){intk=i>ji:jreturnk}}贪心法:publicclassGreedyKnapSack{publicstaticvoidmain(Stringargs){intvalue={,,,}intweigh={,,,}intweight=Knapsack(weight,value,weigh)}privatestaticvoidKnapsack(intweight,intv,intw){intn=vlengthdoubler=newdoublen intindex=newintn for(inti=i<ni) { ri=(double)vi(double)wi indexi=i } 按单位重量价值ri=viwi降序排列doubletemp=for(inti=i<ni){ for(intj=ij<nj){ if(ri<rj){ temp=ri ri=rj rj=temp intx=indexi indexi=indexj indexj=x } } } 排序后的重量和价值分别存到w和v中intw=newintn intv=newintn for(inti=i<ni){ wi=windexi vi=vindexi } Systemoutprintln(ArraystoString(w)) Systemoutprintln(ArraystoString(v)) ints=包内现存货品的重量intvalue=包内现存货品总价值for(inti=i<ni){if(swi<weight){value=vis=wi}}Systemoutprintln("背包中物品的最大总价值为"value)}}回溯法:publicclassBacktrackKnapSack{publicstaticvoidmain(Stringargs){intvalue={,,,}intweigh={,,,}intweight=Knapsack(weight,value,weigh)}privatestaticvoidKnapsack(intweight,intv,intw){intn=vlengthdoubler=newdoublen intindex=newintn for(inti=i<ni) { ri=(double)vi(double)wi indexi=i } 按单位重量价值ri=viwi降序排列doubletemp=for(inti=i<ni){ for(intj=ij<nj){ if(ri<rj){ temp=ri ri=rj rj=temp intx=indexi indexi=indexj indexj=x } } } 排序后的重量和价值分别存到w和v中intw=newintn intv=newintn for(inti=i<ni){ wi=windexi vi=vindexi } 调用函数KnapSackBackTrack()输出打印装完物品以后的最大价值KnapSackBackTrack(w,v,wlength,weight) }privatestaticvoidKnapSackBackTrack(intw,intv,intlength,intweight){intCurrentWeight=intCurrentValue=intmaxValue=inti=intn=vlengthwhile(i>=){if(CurrentWeightwi<weight){CurrentWeight=wiCurrentValue=vii}elsebreak}if(i<n){maxValue=CurrentValueSystemoutprintln("背包中物品的最大总价值为"maxValue)}}}分支限界算法:packagebagbimportjavautilArrayListpublicclassbagdo{publicstaticvoidmain(Stringargs){TODOAutogeneratedmethodstubArrayList<object>objects=newArrayList<>()objectsadd(newobject(,))objectsadd(newobject(,))objectsadd(newobject(,))bagb=newbag(,objects)bfindmaxvalue()bshow()}}packagebagbimportjavautilArrayListimportjavautilCollectionsimportjavautilPriorityQueuepublicclassbag{privateintbagvprivateArrayList<object>objectsprivateintmaxvalueprivateArrayList<object>resultobjectspublicbag(intv,ArrayList<object>o){super()thisbagv=vthisobjects=othismaxvalue=thisresultobjects=Collectionssort(objects)}publicvoidshow(){Systemoutprintln("maxvalue:"thismaxvalue)Systemoutprintln("theobjectwhenmaxvalue:"thisresultobjects)}publicvoidfindmaxvalue(){PriorityQueue<Node>enode=newPriorityQueue<>()Nodenode=newNode(,,bagv,thisobjects)enodeoffer(node)while(true){if(enodeisEmpty())breaknode=enodepoll()if(nodeisend()){thismaxvalue=nodegetbagvalue()thisresultobjects=newArrayList<>(nodegetinbagobject())return}inti=nodegetnodein()objectiobject=thisobjectsget(i)if(nodegetbagweight()iobjectgetweight()<=thisbagv){ArrayList<object>newnodeinbag=newArrayList<object>(nodegetinbagobject())newnodeinbagadd(iobject)intnewnodebagv=nodegetbagleftv()iobjectgetweight()Nodenewnode=newNode(i,newnodeinbag,newnodebagv,thisobjects)enodeadd(newnode)if(newnodegetbagvalue()>thismaxvalue){thismaxvalue=newnodegetbagvalue()thisresultobjects=newArrayList<>(newnodegetinbagobject())}}Nodenewnode=newNode(i,nodegetinbagobject(),nodegetbagleftv(),thisobjects)if(newnodegetbagprio()>thismaxvalue)enodeadd(newnode)}}}packagebagbimportjavautilArrayListpublicclassNodeimplementsComparable<Node>{privateintnodeinprivateArrayList<object>inbagobjectprivateArrayList<object>outbagobjectprivateintleftvprivateintpriopublicNode(inti,ArrayList<object>in,intl,ArrayList<object>out){super()thisnodein=iif(in==)in=newArrayList<>()thisinbagobject=inthisleftv=lthisoutbagobject=outthisprio=thisfindprio()}privateintfindprio(){TODOAutogeneratedmethodstubintbagleft=thisleftvintp=thisgetbagvalue()inti=thisnodeinobjectiobject=while(true){if(i>=thisinbagobjectsize())breakiobject=thisinbagobjectget(i)if(iobjectgetweight()>bagleft)breakbagleft=iobjectgetweight()p=iobjectgetvalue()i}if(i<=thisinbagobjectsize())p=iobjectgetvw()*bagleftreturnp}publicintgetbagweight(){intw=for(objecto:thisinbagobject){w=ogetweight()}returnw}publicintgetbagvalue(){intw=for(objecto:thisinbagobject){w=ogetvalue()}returnw}OverridepublicintcompareTo(Nodeo){TODOAutogeneratedmethodstubif(thisprio>oprio)returnif(thisprio<oprio)returnreturn}publicbooleanisend(){if(thisnodein==thisoutbagobjectsize())returntrue

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/20

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部

举报
资料