ACM程序设计-贪心算法

1、ACM程序设计,2020/7/10,2,贪心算法（Greedy Algorithm）,2020/7/10,3,导引问题：FatMouse Trade,2020/7/10,4,FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean. The warehouse has N rooms. The i-th room contains Ji pounds of JavaBeans and requ

2、ires Fi pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get Ji*a% pounds of JavaBeans if he pays Fi*a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.

3、,2020/7/10,5,Input The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers Ji and Fi respectively. The last test case is followed by two -1s. All integers are not greater t

4、han 1000. Output For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.,2020/7/10,6,Sample Input 5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1 Sample Output 13.333 31.500,2020/7/10,7,所谓“贪心算法”是指：,在对问题

5、求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。 适用于贪心算法策略求解的大多数问题两个特点： 最优子结构：问题的最优解包含了子问题的最有解。 贪心选择性质：可通过做局部最优选择来达到一个数值递增或递减的序关系。,2020/7/10,8,特别说明：,若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！,2020/7/10,9,一、事件序列问题,已知N个事件的发生时刻和结束时刻（见下表，表中事件已按结束时刻升序排序）。一些在时间上没有重叠的事件，可以构成一个事件序列，如

6、事件 2，8，10。事件序列包含的事件数目，称为该事件序列的长度。请编程找出一个最长的事件序列。,2020/7/10,10,算法分析：,不妨用Begini和Endi表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1a2an，满足： Begina1Enda1= BeginanEndan,可以证明，如果在可能的事件a1a2an中选取在时间上不重叠的最长序列，那么一定存在一个包含a1（结束最早）的最长序列。 （证明：略）,2020/7/10,11,算法设计：,从结束时间最早的事件开始 以后各步从开始事件大于上一步结束事件的事件中寻找最先结束的事件。 事件复杂度O(N) N-总事件数

7、,2020/7/10,12,二、区间覆盖问题,用i来表示x轴上坐标为i-1,i的区间（长度为1），并给出M(1=M=200)个不同的整数，表示M个这样的区间。现在让你画几条线段覆盖住所有的区间，条件是：每条线段可以任意长，但是要求所画线段之和最小，并且线段的数目不超过N(1=N=50)。 例如：M=5个整数1、3、4、8和11表示区间，要求所用线段不超过N=4条 0 1 2 3 4 5 6 7 8 9 10 11,2020/7/10,13,算法分析：,如果N=M，那么显然用M条长度为1的线段可以覆盖住所有的区间，所求的线段总长为M。 如果N=1，那么显然所需线段总长为： 如果N=2，相当于N=

8、1的情况下从某处断开（从哪儿断开呢？）。 如果N=k呢？,给定实直线上的n个点，用固定长度的闭区间覆盖这n个点，至少需要多少个这样的闭区间？ 有一本书总共有n页，你可以查询n次，而且它告诉你每一次可以查询的页码为ai = i = bi,即从第ai页到第bi页。问你最少可以查询几次能把这本书所有的页码都可以查询到。,区间覆盖问题的引申：,2020/7/10,15,三、删数问题,键盘输入一个正整数N（不超过240位），去掉其中任意S个数字后剩下的数字按原左右次序组成一个新的正整数。编程对于给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。 输入数据不需判错 输出应包括所去掉的数字的位置和组成

9、的新的正整数。,2020/7/10,16,算法分析,以字符串形式输入N，使用尽可能逼近目标的贪心算法逐一删去其中S个数符，每一步总是选择一个使剩下的数最小的数符删去。之所以作出这样的贪心的选择，是因为删S个数符的全局最有解，包含了删一个数符的子问题的最优解。 为了保证删一个数符后的数最小，按高位到低位搜索递减区间。若不存在递减区间，则删尾数符；否则删递减区间的首字符。,2020/7/10,17,四、Moving Tables,Sample Input 3 4 10 20 30 40 50 60 70 80 2 1 3 2 200 3 10 100 20 80 30 50,Sample Outp

10、ut 10 20 30,2020/7/10,18,算法分析：,1、如果没有交叉，总时间应该是多少？ 2、影响搬运时间的因素是什么？ 3、如果每趟处理都包含最大重叠，处理后的效果是什么？ 4、得出什么结论？,2020/7/10,19,贪心算法的基本步骤,1、从问题的某个初始解出发。 2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。 3、将所有部分解综合起来，得到问题的最终解。,2020/7/10,20,五、The Horse Racing,ACM-ICPC Asia Regional, 2004, Shanghai,2020/7/10,21

11、,示意图：,2020/7/10,22,Case 1:,King: 200 180 160 Tianji: 190 170 150 Ti最快的马比K最快的马慢，则用最慢的马与K的最快的马比。,2020/7/10,23,Case 2:,King: 200 180 175 Tianji: 200 170 150 Ti最快的马与K最快的马等速，则将最慢的马与K的最慢的马比，如果Ti的马慢，则将它与K的最快的马比赛。,2020/7/10,24,Case 3:,King: 200 180 160 Tianji: 200 175 170 Ti最快的马与K最快的马等速，则将最慢的马与K的最慢的马比，如果Ti的

12、马快，则将它们比赛。,2020/7/10,25,提醒：,很多贪心类型的题目都象本题一样，不是最朴素的贪心，而是需要做一些变化，对于我们，关键是找到贪心的本质！,2020/7/10,26,六、部分背包问题,有一个窃贼在偷一家商店时发现有N件物品：第i件物品值Vi元，重Wi磅，这里Vi和Wi都是整数。他希望带走的东西越值钱越好，但他的背包最多只能装下W磅的东西（W为整数）。如果允许小偷可带走某个物品的一部分，小偷应带走哪几件东西，每件东西的重量是多少？,2020/7/10,27,算法分析,按照贪心算法，窃贼开始时对具有最大的每磅价值的物品尽量多拿一些。如果他拿完该物品后仍可以取一些其它物品时，他就再取具有次大的每磅价值的物品，一直继续下