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

贪婪算法姓名:学号:学院:软件工程班级:软件1027班目录课题简述贪婪算法研究框架会场安排找零问题背包问题五子棋游戏结果展示总结致谢课题简述贪婪算法求解最优化问题,很多问题都可以用贪婪算法来求解,比如背包问题,会场活动安排等,其应用范围虽然比较广,但也有其应用的限制。贪婪算法之所以是贪心的,则是希望它的每一步决策都是正确的,即在算法的每一步上,仅根据最优量度标准选择分量,并满足其所得不违反约束条件,最后得到的解不仅是可行的,而且是最优的。事实上最优量度标准并不是整体考虑的,而是在局部某种意义上最优的,所以说每一步决策只是在当前看来是最优的,所以贪婪算法并不能保证对所有问题得到整体最优解。贪婪算法研究框架贪婪算法会场活动找零问题背包问题五子棋课题是针对于算法应用的研究,所以论文先概述了贪婪算法,然后描述了几个应用,总体框架如下:会场安排会场活动安排,在一个固定的会场内希望尽可能多的安排活动个数,得到一个用贪婪算法得到的最优方案:在会场活动安排中,得到一个会场活动时间安排的集合,用一个数组表示,然后比较一个活动时间结束时间和下一个的开始时间,如果ei<fj,则可以选入活动publicstaticvoidGreedySelected(intn,int[]s,int[]f,boolean[]a){ intb=-1; a[0]=true; intj=1; for(inti=1;i<=b;i++){ if(s[i]>=f[j]){//判断选中的活动时间是否大于即将结束活动的时间 a[i]=true; j=i; }else a[i]=false;}}如果输入的结束时间不是非递减的,则将结束时按照照非递减排序好,方便选择比较:publicstaticvoidsort(intn,ints[],intf[],intnum[]){//无序的活动按照结束时间递增 inti,j,m; for(i=0;i<n;i++) for(j=i;j<n-1;j++){ if(f[j]>f[j+1]){ m=f[j]; f[j]=f[j+1]; f[j+1]=m; m=s[j]; s[j]=s[j+1]; s[j+1]=m; m=num[j]; num[j]=num[j+1]; num[j+1]=m; } }找零问题找零钱问题是日常生活中经常遇到的问题,比如找零钱数的多少,一般找零时都会从最大面值找起,依次向下,这是很明显的贪婪算法思想在日常生活的运用输入找零的钱数后,会依次的将找零的钱数从最大面值找起,然后就会有一个找零的方案,找零问题贪婪算法的体现publicstaticint[]zhaoqian(intm[],intn){ intk=; int[]num=newint[k]; for(inti=0;i<k;i++){ num[i]=n/m[i];//num是每一个面值的个数 n=n%m[i];//n值是变值} returnnum; }找零问题的函数调用和输出结果:intm[]={25,10,5,1}; intn=(("请输入找零的钱数:")); ("请输入找零的钱数(元):"+"\n"); int[]num=newint[]; num=zhaoqian(m,n);//调用函数 (n+"元的找钱方案:"+"\n"); for(inti=0;i<;i++){ (num[i]+"枚"+m[i]+"面值"+"\n");