ACM程序设计-贪心算法

ACM程序设计2020/1/272贪心算法（GreedyAlgorithm）2020/1/273导引问题：FatMouse'Trade2020/1/274FatMousepreparedMpoundsofcatfood,readytotradewiththecatsguardingthewarehousecontaininghisfavoritefood,JavaBean.ThewarehousehasNrooms.Thei-throomcontainsJ[i]poundsofJavaBeansandrequiresF[i]poundsofcatfood.FatMousedoesnothavetotradeforalltheJavaBeansintheroom,instead,hemaygetJ[i]*a%poundsofJavaBeansifhepaysF[i]*a%poundsofcatfood.Hereaisarealnumber.Nowheisassigningthishomeworktoyou:tellhimthemaximumamountofJavaBeanshecanobtain.2020/1/275InputTheinputconsistsofmultipletestcases.Eachtestcasebeginswithalinecontainingtwonon-negativeintegersMandN.ThenNlinesfollow,eachcontainstwonon-negativeintegersJ[i]andF[i]respectively.Thelasttestcaseisfollowedbytwo-1‘s.Allintegersarenotgreaterthan1000.OutputForeachtestcase,printinasinglelinearealnumberaccurateupto3decimalplaces,whichisthemaximumamountofJavaBeansthatFatMousecanobtain.2020/1/276SampleInput53724352203251824151510-1-1SampleOutput13.33331.5002020/1/277所谓“贪心算法”是指：在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。适用于贪心算法策略求解的大多数问题两个特点：最优子结构：问题的最优解包含了子问题的最有解。贪心选择性质：可通过做局部最优选择来达到一个数值递增或递减的序关系。2020/1/278特别说明：若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！！2020/1/279一、事件序列问题已知N个事件的发生时刻和结束时刻（见下表，表中事件已按结束时刻升序排序）。一些在时间上没有重叠的事件，可以构成一个事件序列，如事件{2，8，10}。事件序列包含的事件数目，称为该事件序列的长度。请编程找出一个最长的事件序列。事件编号01234567891011发生时刻130325641081515结束时刻34789101214151819202020/1/2710算法分析：不妨用Begin[i]和End[i]表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1a2…an，满足：Begin[a1]End[a1]=…=Begin[an]End[an]可以证明，如果在可能的事件a1a2…an中选取在时间上不重叠的最长序列，那么一定存在一个包含a1（结束最早）的最长序列。（证明：略）2020/1/2711算法设计：从结束时间最早的事件开始以后各步从开始事件大于上一步结束事件的事件中寻找最先结束的事件。事件复杂度O(N)N-总事件数2020/1/2712二、区间覆盖问题用i来表示x轴上坐标为[i-1,i]的区间（长度为1），并给出M(1=M=200)个不同的整数，表示M个这样的区间。现在让你画几条线段覆盖住所有的区间，条件是：每条线段可以任意长，但是要求所画线段之和最小，并且线段的数目不超过N(1=N=50)。例如：M=5个整数1、3、4、8和11表示区间，要求所用线段不超过N=4条012345678910112020/1/2713算法分析：如果N=M，那么显然用M条长度为1的线段可以覆盖住所有的区间，所求的线段总长为M。如果N=1，那么显然所需线段总长为：…如果N=2，相当于N=1的情况下从某处断开（从哪儿断开呢？）。如果N=k呢？给定实直线上的n个点，用固定长度的闭区间覆盖这n个点，至少需要多少个这样的闭区间？有一本书总共有n页，你可以查询n次，而且它告诉你每一次可以查询的页码为ai=i=bi,即从第ai页到第bi页。问你最少可以查询几次能把这本书所有的页码都可以查询到。区间覆盖问题的引申：2020/1/2715三、删数问题键盘输入一个正整数N（不超过240位），去掉其中任意S个数字后剩下的数字按原左右次序组成一个新的正整数。编程对于给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。输入数据不需判错输出应包括所去掉的数字的位置和组成的新的正整数。2020/1/2716算法分析以字符串形式输入N，使用尽可能逼近目标的贪心算法逐一删去其中S个数符，每一步总是选择一个使剩下的数最小的数符删去。之所以作出这样的贪心的选择，是因为删S个数符的全局最有解，包含了删一个数符的子问题的最优解。为了保证删一个数符后的数最小，按高位到低位搜索递减区间。若不存在递减区间，则删尾数符；否则删递减区间的首字符。2020/1/2717四、MovingTablesSampleInput341020304050607080213220031010020803050SampleOutput1020302020/1/2718算法分析：1、如果没有交叉，总时间应该是多少？2、影响搬运时间的因素是什么？3、如果每趟处理都包含最大重叠，处理后的效果是什么？4、得出什么结论？2020/1/2719贪心算法的基本步骤1、从问题的某个初始解出发。2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。3、将所有部分解综合起来，得到问题的最终解。2020/1/2720五、TheHorseRacingACM-ICPCAsiaRegional,2004,Shanghai2020/1/2721示意图：928371748795928371748795-200-200-200928371748795-200+200+2002020/1/2722Case1:King:200180160Tianji:190170150Ti最快的马比K最快的马慢，则用最慢的马与K的最快的马比。2020/1/2723Case2:King:200180175Tianji:200170150Ti最快的马与K最快的马等速，则将最慢的马与K的最慢的马比，如果Ti的马慢，则将它与K的最快的马比赛。2020/1/2724Case3:King:200180160Tianji:200175170Ti最快的马与K最快的马等速，则将最慢的马与K的最慢的马比，如果Ti的马快，则将它们比赛。2020/1/2725提醒：很多贪心类型的题目都象本题一样，不是最朴素的贪心，而是需要做一些变化，对于我们，关键是找到贪心的本质！2020/1/2726六、部分背包问题有一个窃贼在偷一家商店时发现有N件物品：第i件物品值Vi元，重Wi磅，这里Vi和Wi都是整数。他希望带走的东西越值钱越好，但他的背包最多只能装下W磅的东西（W为整数）。如果允许小偷可带走某个物品的一部分，小偷应带走哪几件东西，每件东西的重量是多少？2020/1/2727算法分析按照贪心算法，窃贼开始时对具有最大的每磅价值的物品尽量多拿一些。如果他拿完该物品后仍可以取一些其它物品时，他就再取具有次大的每磅价值的物品，一直继续下去，直到不能取为止。2020/1/2728练习题(北大ACM)1017104210651083108912301323132814771505152117001716178417551828186218741909192220542082210922092313232523362370239325862709