《贪心算法的实验总结(共10篇)》由会员分享，可在线阅读，更多相关《贪心算法的实验总结(共10篇)（28页珍藏版）》请在金锄头文库上搜索。
1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划贪心算法的实验总结(共10篇)实验报告题目实验四贪心算法开课实验室：数学实验室指导老师：韩逢庆时间：学院：理学院专业：信息与计算科学班级：XX级2班姓名：古月学号：一、实验目的1加深学生对贪心算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2提高学生利用课堂所学知识解决实际问题的能力；3提高学生综合应用所学知识解决实际问题的能力。二、实验内容题目见P143:4-16,4-23.三、实验要求用分治法求解最少加油次数和最少硬币个数问题；再选择自己熟悉的其它方法求解本问题；上机实现
2、所设计的所有算法；四、实验过程设计最少加油次数实验题目一辆汽车加满油以后可以行使n公里，旅途中有若干个加油站，设计一个有效算法，指出应在哪些加油站停靠加油，使沿路加油次数最少。并证明算法能产生一个最优解。过程设计贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说最少加油次数的问题。在这个算法中，我采用的贪心算法的策略。首先人机互动的设定加满油以后最长能够行使的距离，然后输入了各个站点之间的距离，在
3、程序的设计中，首先检查了程序的可行性。要是遇到当某两个站点之间的距离大于汽车一次加油以后所能够行使的最大距离时，我们认为此问题是不可行的。这个在实际情况中也是很容易理解的。然后在满足可行性条件下，依次采用贪心算法对问题得以实现。采用s这个来保存现在车里面留下的油，当此时留下的有能够行驶完这一站点到下一站点之间的距离是，在这一站点的时候就不加油。但是若不能行使完这一段路程的时候，就加满油。核心算法如下：for(i=0,s=0;in)sum+;s=ai;最少硬币个数问题实验题目考虑下面的用最少硬币个数找出n分钱的问题：当使用2角5分，1角，5分和1分四种硬币面值时，设计一个找n分钱的贪心算法，并证
4、明算法能产生最优解。过程设计贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说找最少硬币个数的问题。在算法的实现过程中，当剩余的钱数大于2角5分时，我们在记录找2角5分硬币的个数的变量里面加一，同时把剩余所找的钱的总数目也减2角5分。不断重复这个过程，直到剩余所需找的钱的数目小于2角5分时，在记录找1角硬币的个数的变量里面加一，同时把剩余所找的钱的总数目也减1角，不断重复这个过程，直到剩余所需找的
5、钱的数目小于1角。5分和1分的硬币实现过程同上述过程一样，一直执行到所剩的钱的数目为0，此时停止计算，得到最优解。五、实验结果分析最少加油次数当加油后行驶的最大距离小于相邻站点的最小值时，此时，可行，求解结果如下：当加油后行驶的最大距离大于相邻站点的最小值时，此时，没用可行性，为边沿情况，求解结果如下：时间复杂性：该算法的时间复杂度为O(n)空间复杂性分析：该算法的空间复杂度为O(1)最少硬币问题当输入的找零钱数为正常的时候的运行情况如下：当输入的找零钱数为不正常的时候的运行情况如下：时间复杂性：该算法的时间复杂性为O(n)空间复杂性分析：该算法的空间复杂性为O(1)六、实验体会贪心算法总是作
6、出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题，相容活动安排问题福建工程学院计算机与信息科学系实验报告12345福建工程学院计算机与信息科学系实验报告12345篇二：北邮算法作业贪心算法实验报告第三次算法作业姓名：吴迪班级：学号：班内序号15摘要：本文为完成作业problem1，problem3，problem4，problem5的四道贪心算法题。备注：所有后缀为_ex的可执行文
7、件为文件输入输出模式的程序，比如problem1_1特殊的01背包问题描述：01背包是在n件物品取出若干件放在空间为c的背包里，每件物品的体积为w1，w2?wn，与之相对应的价值为p1,p2?pn，并取得最大价值。普通的01背包中物品的重量和价值没有明确的关系，这里定义一种特殊的01背包：向背包中放入的物品的价值和体积成反比，也就是价值越高，体积越小，注意这里物品价值和体积的乘积并不是固定值。例如：如下的物品满足这个“特殊的01背包”,5件物品:物品1,价值v=6,体积w=20物品2,价值v=1,体积w=60物品3,价值v=20,体积w=3物品4,价值v=15,体积w=15物品5,价值v=99
8、,体积w=1假如我有一个容量为c的背包,c=20，那么选择物品3、4、5可以获得最大价值134。输入：首先是一个整数t,代表测试数据的组数。每组测试数据首先是两个正整数n和c，n代表物品的个数，c代表背包的最大容积。然后有n行整数，每行有两个整数，分别代表物品的价值v和体积w。t的范围是(1-100),n的范围是(1-),c、v、w的范围不超过四字节的int型。输出：首先输出测试数据的组号，例如第一组的组号为“case1:”，占一行。然后是一个整数，代表可以取得的最大价值，占一行。sampleinput:552062016020315159911192171011093181093961396
9、188917106171408627833178319545510378233753599109421535695169120396982285454110242676546sampleoutput:case1:134case2:case3:109case4:212case5:312问题分析:本题是特殊的01背包问题，由于其价值和重量的反比规律易证明贪婪算法的有效性，故本题可以采用贪心算法求解，即每次优选最轻物品也是最大价值物品。源代码：#include#includeusingnamespacestd;intgreedy_calculate(int*v,int*w,constintn,con
10、stintc);intmain()/inputintt;/testgroupnum1-100intn;/objectnum1-intc;/capacityint*v;int*w;fstreamin;fstreamout;(problem1_,ios:in);(problem1_,ios:out);int;if(t100|tn;if(n|nc;if(cvj;inwj;/outputoutc)total_value-=vlw_num;total_weight-=wlw_num;deletex;returntotal_value;运行截图篇三：算法实验报告贵州大学计算机科学与技术学院计算机科学与技术
11、系上机实验报告贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告篇四：贪心算法解汽车加油问题实验报告一、实验名称：用贪心算法、回溯算法、动态规划等解决汽车加油次数最少问题。二、实验目的：课程设计是计算机算法与设计课程不可缺少的重要实践性环节。通过实践教学，要达到以下目的：使学生掌握线性表、栈、队列、串、树、二叉树、图、集合等各种典型抽象数据类型的数学模型及其所支持基本运算的实现方法；使学生掌握以抽象数据类型为模块的面向对象程序设计方法；使学生提高对实际问题的分析、设计和实现能力；为学生后续课程的学习及课程设计打下坚实的实践基础。三、使用的策略：贪心算法、回溯算法等。四、实验内容：问题描
12、述一辆汽车加满油后可以行驶n千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。给出n，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越快越好。问题分析对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为ai；i=0，1，2，3?n1.始点到终点的距离小于，则加油次数k=0；2.始点到终点的距离大于n，a加油站间的距离相等，即i=aj=l=n，则加油次数最少k=n；b加油站间的距离相等，即i=aj=ln，则不可能到达终点；c加油站间的
13、距离相等，即i=aj=l#includevoidopen_file(intn)FILE*fp;if(fp=fopen(,wt)=NULL)printf(thefilewritefailed.n);exit(1);fprintf(fp,%2dn,n);fclose(fp);voidsave_file(intsum)FILE*fp;if(fp=fopen(,wt)=NULL)printf(thefilesavefailed!.n);exit(1);fprintf(fp,%2dn,sum);fclose(fp);if(fp=fopen(,r)=NULL)printf(savefilefailed!n);exit(1);fscanf(fp,%2d,&sum);printf(n鏈澶?dn,sum);fclose(fp);intMAX(intn)inti=2,j=0,datan,sum=0,max=1;intlenth;while(sum+i0)if(j#include#includeusingnamespacestd;constintV=9;/定义顶点个数/从未包含在SPT的集合T中，选取一个到S集合的最短距离
