毕业答辩-贪婪算法系统设计.ppt

,贪婪算法,姓名：学号：学院：软件工程班级：软件1027班,目录,课题简述贪婪算法研究框架会场安排找零问题背包问题五子棋游戏结果展示总结致谢,课题简述,贪婪算法求解最优化问题，很多问题都可以用贪婪算法来求解，比如背包问题，会场活动安排等，其应用范围虽然比较广，但也有其应用的限制。贪婪算法之所以是贪心的，则是希望它的每一步决策都是正确的，即在算法的每一步上，仅根据最优量度标准选择分量，并满足其所得不违反约束条件，最后得到的解不仅是可行的，而且是最优的。事实上最优量度标准并不是整体考虑的，而是在局部某种意义上最优的，所以说每一步决策只是在当前看来是最优的，所以贪婪算法并不能保证对所有问题得到整体最优解。,贪婪算法研究框架,课题是针对于算法应用的研究，所以论文先概述了贪婪算法，然后描述了几个应用，总体框架如下：,会场安排,会场活动安排，在一个固定的会场内希望尽可能多的安排活动个数，得到一个用贪婪算法得到的最优方案：,在会场活动安排中，得到一个会场活动时间安排的集合，用一个数组表示，然后比较一个活动时间结束时间和下一个的开始时间，如果ei=fj)/判断选中的活动时间是否大于即将结束活动的时间ai=true;j=i;elseai=false;,如果输入的结束时间不是非递减的，则将结束时按照照非递减排序好，方便选择比较：publicstaticvoidsort(intn,ints,intf,intnum)/无序的活动按照结束时间递增inti,j,m;for(i=0;ifj+1)m=fj;fj=fj+1;fj+1=m;m=sj;sj=sj+1;sj+1=m;m=numj;numj=numj+1;numj+1=m;,找零问题,找零钱问题是日常生活中经常遇到的问题，比如找零钱数的多少，一般找零时都会从最大面值找起，依次向下，这是很明显的贪婪算法思想在日常生活的运用,输入找零的钱数后，会依次的将找零的钱数从最大面值找起，然后就会有一个找零的方案，找零问题贪婪算法的体现publicstaticintzhaoqian(intm,intn)intk=m.length;intnum=newintk;for(inti=0;ik;i+)numi=n/mi;/num是每一个面值的个数n=n%mi;/n值是变值returnnum;,找零问题的函数调用和输出结果：intm=25,10,5,1;intn=Integer.parseInt(JOptionPane.showInputDialog(请输入找零的钱数：);ta.append(请输入找零的钱数(元)：+n);intnum=newintm.length;num=zhaoqian(m,n);/调用函数ta.append(n+元的找钱方案：+n);for(inti=0;im.length;i+)ta.append(numi+枚+mi+面值+n);,背包问题,背包问题是向背包中装入收益最大的东西，并且可以使得背包的没有剩余重量的浪费，所以用贪婪算法解决背包装入的方案,背包问题输入背包重量，输入背包物品的重量，输入背包问题的价值，贪婪算法按照单位收益价值最大来实现装满背包，用哈希表来存放物品单位收益价值x=newfloats1;HashMapmap=newHashMap();for(inti=0;is1;i+)xi=pi/wi;map.put(xi,i);ta.append(第+(i+1)+个物品的价格容量比为+Float.toString(xi)+n);,背包问题将单位收益值按照从大到小的顺序进行排序inti1,j;floattemp;for(i1=0;i1x.length;i1+)for(j=0;jx.length-i1-1;j+)if(xj)(xj+1)temp=xj;xj=xj+1;xj+1=temp;ta.append(从大到小输出价格容量比为：+n);for(i1=0;i1x.length;i1+)ta.append(Float.toString(xi1)+n);ta.append(其对应的序号为+n);intsort=newints1;for(i1=0;i1x.length;i1+)ta.append(Integer.toString(map.get(xi1)+n);sorti1=map.get(xi1);,背包问题装入背包的方案for(y=0;ys)xt=s/wt;s=0;ta.append(Float.toString(sorty+1)+Float.toString(xt)+n);elseif(wt=s)xt=1;s=0;ta.append(Float.toString(sorty+1)+Float.toString(xt)+n);elseif(wts)xt=1;s-=wt;ta.append(Float.toString(sorty+1)+Float.toString(xt)+n);,五子棋游戏,人机对战电脑下棋的实现可以用到贪婪算法，贪婪算法可以实现人与电脑下棋的电脑走棋，所以在贪婪算法的算法思想下，可以实现五子棋游戏的电脑下棋,五子棋游戏中贪婪算法的体现：for(i=1;i=size;i+)/遍历整个棋盘for(j=1;j=size;j+)if(mapij=0)/这点能下棋，则求下在这里的权值robotscore=getscore(newPoint(i,j),col);/得到机器人下在这点的权值if(robotscore=MAX)return(newPoint(i,j);/如果下在这里已经赢了，则返回此点opponentscore=getscore(newPoint(i,j),-col);/得到对手下在这点的权值,五子棋游戏中，不断遍历棋盘中没有下子的地方，下一次棋就计算依次权值，每一次都在权值最大的地方下棋，然后这一走法体现了贪婪算法的思想,结果展示,主题界面展示：,点击贪婪简介：,贪婪实例：,出品人：,五子棋游戏：,会场活动,找零钱,背包问题,人机对战：,总结,贪婪算法只有