实验三01背包问题不同算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
、
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
与对比一.问题描述给定种物品和一背包。物品的重量是,其价值为,背包的容量为c问题:应如何选择装入背包中的物品,使得装入背包中物品的总价值最大。说明:在选择装入背包的物品时,对每种物品只有两个选择,装入背包或不装入背包,也不能将物品装入背包多次。二.实验内容与要求实验内容:分析该问题适合采用哪些算法求解(包括近似解)。动态规划、贪心、回溯和分支限界算法。分别给出不同算法求解该问题的思想与算法设计,并进行算法复杂性分析。动态规划:递推方程:时间复杂度为贪心法:算法思想:贪心原则为单位价值最大且重量最小,不超过背包最大承重量为约束条件。也就是说,存在单位重量价值相等的两个包,则选取重量较小的那个背包。但是,贪心法当在只有在解决物品可以分割的背包问题时是正确的贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。用贪心法设计算法的特点是一步一步地进行根据某个优化测度(可能是目标函数,也可能不是目标函数),每一步上都要保证能获得局部最优解。每一步只考虑一个数据,它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加为止。回溯法:回溯法:为了避免生成那些不可能产生最佳解的问题状态,要不断地利用限界函数(boundingfunction)来处死那些实际上不可能产生所需解的活结点,以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。对于有n种可选物品的0/1背包问题,其解空间由长度为n的0-1向量组成,可用子集数
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示。在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。时间复杂度为:O(2n)空间复杂度为:O(n)分支限界算法:首先,要对输入数据进行预处理,将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中,节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点,则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点,仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。设计并实现所设计的算法。对比不同算法求解该问题的优劣。这动态规划算法和贪心算法是用来分别解决不同类型的背包问题的,当一件背包物品可以分割的时候,使用贪心算法,按物品的单位体积的价值排序,从大到小取即可。当一件背包物品不可分割的时候,(因为不可分割,所以就算按物品的单位体积的价值大的先取也不一定是最优解)此时使用贪心是不对的,应使用动态规划。设计方法时间复杂度优点缺点动态规划{可求得最优决策序列速度慢贪心方法()速度较快很难得到最优解回溯法(2能够得到最优解时间复杂度较高分支限界法()速度较快,易求解占用内存大,效率不高需要提交不同算法的实现代码和
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
报告。动态规划方法:publicclassKnapsack{publicstaticvoidmain(String[]args){int[]value={0,60,100,120};int[]weigh={0,10,20,30};intweight=50;Knapsackl(weight,value,weigh);publicstaticvoidKnapsack1(intweight,int[]value,int[]weigh){int[]v=newint[value.length];int[]w=newint[weigh.length];int[][]c=newint[value.length][weight+1];intd[]=newint[100];for(inti=0;i
j?i:j;returnk;}}贪心法:publicclassGreedyKnapSack{publicstaticvoidmain(String[]args){int[]value={0,60,100,120};int[]weigh={0,10,20,30};intweight=50;Knapsackl(weight,value,weigh);}privatestaticvoidKnapsack1(intweight,int[]v,int[]w){intn=v.length;double[]r=newdouble[n];int[]index=newint[n];for(inti=0;i=0){if(CurrentWeight+w1[i]objects=newArrayList<>();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.ArrayList;importjava.util.Collections;importjava.util.PriorityQueue;publicclassbag{privateintbagv;privateArrayList
本文档为【01背包问题不同算法设计、与对比讲解1】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。