实验二(贪心算法)

华东师范大学计算机科学技术系学生上机实践报告第1页共9页华东师范大学计算机科学技术系上机实践报告课程名称：算法设计与分析年级：05上机实践成绩：指导教师：柳银萍姓名：张翡翡上机实践名称：贪心算法学号：10052130119上机实践日期：2007-4-10上机实践编号：NO.2组号：上机实践时间：10:00-11:30一、目的了解熟悉掌握贪心算法实质并学会灵活运用，从而解决生活中一些实际问题。二、内容与设计思想1.超市的自动柜员机(POS)要找给顾客各种数值的现金，表面上看，这是一个很简单的任务，但交给机器办就不简单了。你作为一个计算机专家，要求写一个程序来对付这个“简单”的问题。你的自动柜员机有以下的币种：100元，50元，20元，10元，5元，2元，1元。你可以假设每种钱币的数量是无限的。现在有一笔交易，需要找个客户m元，请你设计一个算法，使得找给顾客的钱币张数最少。要求：输入：第一行仅有一个整数n(0n=10000),表示有几组测试数据。每组测试数据仅有一行，每行只有一个整数m(0m2000000000)，表示需要找的钱币数。(提示：对于大量的输出，请使用scanf,不要使用cin)输出：每组测试数据输出一行，每行有7个整数(两两之间有一个空格，结尾不能有空格)，表示100元，50元，20元，10元，5元，2元，1元所需要的张数。1.1其思路是：1)定义相关变量；2)接收相关数据，如测试数据组数n和要找的钱币数；3)依次考虑100，50，20，10，5，2，1的需要找的钱币张数，用最简单的加减乘除；4)输出其值。1.2具体算法是：while(n--)m输入a=m/100b=(m-100*a)/50c=(m-100a-50b)/20d=(m-100a-50b-20c)/10e=(m-100a-50b-20c-10d)/5f=(m-100a-50b-20c-10d-5e)/2g=m-100a-50b-20c-10d-5e-2f华东师范大学计算机科学技术系学生上机实践报告第2页共9页endwhile2.若在0-1背包问题中各物品是依重量递增排列时，其价值恰好依递减序排列。对这个特殊的0-1背包问题，请设计一个有效算法找出最优解，并证明算法的正确性。要求：输入：输入只有四行，第一行有一个正数n（n=10000）为物品的数量。第二行有n个递增的整数表示每一个物品的重量。第三行有n个递减的整数，表示每个物品的价值。最后一行有一个整数w表示背包的容量。所有数据均小于1000000。输出：输出背包可带走物品的最大价值。2.1其思路是：1)定义相关变量及赋初值；2)接收相关数据如物品的数量，每个物品的重量及每个物品的价值，以及背包的容量；3)写两个排序函数，一个递增一个递减；4)用一个循环判断装进的重量是否超过背包容量；5)最后输出所装下的容量大小。2.2具体算法是：n输入fori0tona[i]输入fori0tonb[i]输入w输入kifori0tonforji+1tonifa[k]a[j]thenk=jt=a[i]a[i]=a[k]a[k]=tkifori0tonforji+1tonifb[k]b[j]thenk=jt=b[i]b[i]=b[k]b[k]=tfori0ton华东师范大学计算机科学技术系学生上机实践报告第3页共9页max+=a[i]ifmax=wthensum+=b[i]return(0)2.3算法的正确性证明：3．一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。对于给定的n(n=5000)和k(k=1000)个加油站位置，编程计算最少加油次数。要求：输入：第一行有2个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。输出：输出编程计算出的最少加油次数。如果无法到达目的地，则输出”NoSolution”。3.1其思路是：1)定义相关变量及赋初值；2)接收相关数据如加满油能行驶的距离，加油站个数和各加油站之间的距离；3)考虑特殊情况：(1)如果起点到第一个加油站距离大于加满油时能行驶距离，则输出“NoSolution!”(2)如果七次加满油和起始站加满油之和能行驶距离小于起点到终点距离，则输出“NoSolution”4)for循环处理各个站情况，如果剩余的油能行驶的距离大于到下一个站的距离，则不用再加油，如果剩余的油能行驶的距离小于到下一个站的距离，则加满油，如果加满油还是小于则输出“NoSolution”，否则使计数m加一；5)最后输出m的值。3.2具体算法是：n输入k输入fori0toka[i]输入sum+=a[i]ifna[0]thenprintf(NoSolution!)elseifn*(k+1)sumthenprintf(NoSolution!)elseleft=n-a[0]华东师范大学计算机科学技术系学生上机实践报告第4页共9页fori1tokiflefta[i]thenleft-=a[i]elset=n+leftifta[i]thenprintf(NoSolution!)elseleft=t-a[i]m+=1printf(m)return(0)三、使用环境MicrosoftvisualC++6.0四、调试过程1.有时候太大意，第一次调试时居然忘了打“*”符号，导致出现一大堆错误，我用的是最笨的办法来算钱币数，其实知道还有更优的方法去解决，之后还可以再研究研究，还出现一个问题就是粗心，“/”号打成“%”号导致结果错误甚至出现一堆乱码类东西。2.做第二个程序基本没什么大问题，只是刚开始的时候排序函数没有单独写出来导致测试不正确，还有一开始没有在main()函数中定义调用的两个排序函数，最粗心的是将两个函数相反了一下，即把重量按升序排，价值按减序排导致结果很离谱。还有一个问题是最后一个for语句判断重量有没有超过背包总重量时只是加出来总重量，即在b[i]的地方写成了a[i]，不过好在都是小错误。3.第三个程序很顺利，只是在审题的时候考虑地太过复杂，考虑了比如现在第一个站它能开到第二个站，但是第二个站到第三个站即使加满油也不能开到的时候，我再考虑是不是该在第一个站加上油这样就能够从第二站到第三站，问题就变得复杂多了。调试过程只有一个地方出现问题就是考虑了剩余油能行驶距离如果小于接下来要行驶的距离，而忘了处理如果剩余油大于接下来能行驶距离情况下的left的值的改变。经过一步一步调试而处理好。五、总结基础虽然简单但有时候还是要掌握牢固才好，粗心有时候会耽误很多不必要的时间要尽量克服，在写程序的时候认真才行。有时候还是不能偷懒，要尽量想想其他更优的方法，比如第一个程序我用的就是最笨最原始的方法，很显然复杂度可能就大了。基础不扎实，在调用函数的时候在开头没有定义，不过经同学指点就可以改，应该学会更深一层思考以及用多种不同的方法实现，比如排序方法有很多种，可以借此机会多思考采用各种排序方法，从而巩固了以前的知识。考虑问题要全面，虽然有时候会将问题复杂化但是至少思考过程能学到很多东西，这样会使逻辑越来越严谨。华东师范大学计算机科学技术系学生上机实践报告第5页共9页六、附录1.找零钱问题的程序：（此处放程序）#includestdio.hintmain(){inta,b,c,d,e,f,g,n,m;scanf(%d,&n);while(n--){scanf(%d,&m);a=m/100;b=(m-100*a)/50;c=(m-100*a-50*b)/20;d=(m-100*a-50*b-20*c)/10;e=(m-100*a-50*b-20*c-10*d)/5;f=(m-100*a-50*b-20*c-10*d-5*e)/2;g=m-100*a-50*b-20*c-10*d-5*e-2*f;printf(%d%d%d%d%d%d%d\n,a,b,c,d,e,f,g);}return(0);}运行结果：华东师范大学计算机科学技术系学生上机实践报告第6页共9页2.0-1背包问题的程序：（此处放程序）#includestdio.hintmain(){voidsort1(inta[10000],intn);voidsort2(intb[10000],intn);inta[10000],b[10000];intw,i,n;intmax=0;intsum=0;scanf(%d,&n);for(i=0;in;i++)scanf(%d,&a[i]);for(i=0;in;i++)scanf(%d,&b[i]);scanf(%d,&w);sort1(a,n);sort2(b,n);for(i=0;in;i++){max+=a[i];if(max=w)sum+=b[i];}printf(%d\n,sum);return(0);}voidsort1(inta[10000],intn){inti,j,k;intt;for(i=0;in;i++){k=i;for(j=i+1;jn;j++)if(a[k]a[j])k=j;t=a[i];a[i]=a[k];a[k]=t;华东师范大学计算机科学技术系学生上机实践报告第7页共9页}}voidsort2(intb[10000],intn){inti,j,k;intt;for(i=0;in;i++){k=i;for(j=i+1;jn;j++)if(b[k]b[j])k=j;t=b[i];b[i]=b[k];b[k]=t;}}运行结果:3．汽车加油问题的程序：（此处放程序）#includestdio.hintmain(){intn,k,i,left;inta[1025];华东师范大学计算机科学技术系学生上机实践报告第8页共9页intsum=0;intm=0;intt=0;scanf(%d,&n);scanf(%d,&k);for(i=0;i=k;i++){scanf(%d,&a[i]);sum+=a[i];}if(na[0])printf(NoSolution!);elseif(n*(k+1)sum)printf(NoSolution!);else{left=n-a[0];for(i=1;i=k;i++){if(lefta[i])left-=a[i];elseif(left=a[i]){t=n+left;if(ta[i])printf(NoSolution!);elseleft=t-a[i];m+=1;}}printf(%d\n,m);}return(0);}运行结果:华东师范大学计算机科学技术系学生上机实践报告第9页共9页要求至少给出1组测试数据运行结果。