贪婪算法介绍

浅议贪心法的应用华中科技大学ACM集训队张磊Email:[e-mail]算法设计与ACM编程之道就如武学之道，程序设计的语言如同各门各派的武功招式，算法和数据结构则好比内功心法和武学原理。内力深厚，任何招式到了手上都能够化腐朽为神奇；只有掌握了武学原理,才能做到无招胜有招。常常有人问我,我把程序编出来,能出结果就可以,为什么还要用算法呢?给出例子:最大子序列和问题:给定整数，A1，A2，…AN(可能有负数)．求从i到j的和Ak的最大值(为方便起见。如果所有整数均为负数，则最大子序列和为0)。算法1:算法2:算法3:二分法算法4:时间的分析:一些特定的问题可以做到在精心的算法的指导下,对于大量数据的处理,把时间限制从16年减到1秒贪心法是一种重要的算法设计技术，它总是做出在当前来说是最好的选择，而并不从整体上加以考虑，他所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解。当然，我们也希望贪婪算法得到的最终解是整体的最优解。GreedyAlgorithms贪心法不追求最优解,只求可行解,通俗点讲就是不求最好,只求可好每一步都按贪心准则找一个解,故到n步后（n为问题的规模）得到问题的所有解．如找不到所有解，则修改贪婪准则，放宽贪婪条件或修改算法某些细节，重新从头开始找解．一个简单的贪心问题找零钱问题背包问题:有一个贼在偷窃一家商店时发现有N件物品:第i件物品值vi元，重wi磅，(1=i=n)，此处vi和wi都是整数。他希望带走的东西越值钱越好，但他的背包中最多只能装下W磅的东西(W为整数)。有两种偷窃方式:1)0一1背包问题如果每件物品或被带走或被留下，小偷应该带走哪几件东西?2)部分背包问题如果允许小偷可带走某个物品的一部分,小偷应该带走哪几件东西，每件东西的重量是多少?背包问题部分背包问题(可用贪心)0-1背包问题(不能用贪心)应用贪心法求解问题，首要是要弄清楚贪心准则!每一步所找到的解是这一步中的最优解,但每步最优解形成的整体解并不一定最优.对于一个最优化问题,怎样才知道它是否适用于贪心法求解呢?没有一个通用的方法!但适用于贪心策略求解的大多数问题有两个特点:1贪心选择性质---可通过做局部最优(贪心)选择来达到全局最优解2.最优子结构---问题的最优解包含了子问题的最优解GoneFishing-ACM/ICPCRegionalContestEastCentralNorthAmerica1999题意描述：john现有h个小时的空闲时间，他打算去钓鱼。john钓鱼的地方共有n个湖，所有的湖沿着一条单向路顺序排列（john每在一个湖钓完鱼后，他只能走到下一个湖继续钓），john必须从1号湖开始钓起，但是他可以在..任何一个湖结束他此次钓鱼的行程。题意描述：john在每个湖中每5分钟钓的鱼数（此题中以5分钟作为单位时间），随时间的增长而线性递减。而每个湖中头5分钟可以钓到的鱼数以及每个湖中相邻5分钟钓鱼数的减少量，input中均会给出。并且John从任意一个湖走到它下一个湖的时间input中也都给出。问题：求一种方案，使得john在有限的h小时中可以钓到尽可能多的鱼。output中需包括john在所有湖边所呆的时间，以及最后总的钓鱼数。Sampleinput2-湖的数量1-john有的总时间101-第一个湖中头5分钟可以钓到的鱼数第一个湖中相邻5分钟钓鱼数的减少量252-从第一个湖走到第二个湖的时间Sampleoutput45,5-分别在两个湖中呆的时间Numberoffishexpected:31-钓鱼的总数推荐书籍:1.《数据结构与算法分析》MarkAllenWeiss著，机械工业出版社2.《算法导论》INTRODUCTIONTOALGORITHMSTHTMITPRESS3.入门级,有很好的小例子，清华大学计算机系的专业入门课教材《程序设计基础》吴文虎著，清华大学出版社，推荐大家做题目适应比赛的网站国内的：://acm.zju.edu.cn/本次评测系统：国外的：谢谢!!