2021-10课件acm入门教程7贪心算法

1、ACM 程序设计竞赛入门浙江工业大学田贤忠 2022/9/2612022/9/262第七讲贪心算法（Greedy Algorithm）2022/9/263什么是贪心算法？2022/9/264所谓“贪心算法” ：在对问题求解时，采用逐步构造最优解。也就是说，它要求“贪心”地选择最佳操作，并希望通过一系列局部的最优选择，能够产生一个整个问题的(全局)最优解。决策一旦作出，就不能更改。作为贪婪决策的依据称为贪心准则（Greedy Criterion) 2022/9/265一个简单例子FatMouse Trade2022/9/266HDOJ: 1009FatMouse Trade2022/9/267P

2、roblem Description 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 requires Fi pounds of cat food. FatMouse does not have to trade for all t

3、he 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.2022/9/268Input：The input consists of multiple test cases. Each tes

4、t 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 than 1000.Output ：For each test case, print in a single line a real num

5、ber accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.Sample Input5 3 （5个，有3个交换的地方）7 2 （2换7）4 3 5 2 20 3 25 1824 15 15 10 -1 -1Sample Output13.333 31.5002022/9/269贪心准则：很明显，每次总是先挑最划算的交易，一直把手里的cat food 都换完2022/9/2610算法基本思想：输入（其中，交易数据J , F 对放入数组）对数组排序（按效

6、益，降序）按效益高低进行有序交易，一直把手里的cat food 都换完。输出得到的 Java Beans.2022/9/2611部分参考代码：struct warehouse int bean, food; double r;warehouse a1001;2022/9/2612. sort(a,a+n ,cmp); catfood=m; javabean=0; for(i=0;in;i+) if(ai.foodb.r; 2022/9/2613说明：贪心算法有一种直觉的倾向。找最优装载时，直觉告诉我们如何装载是最多的；交易时，直觉告诉我们如何才划算.采用贪心算法求解某问题的最优解，必须首先证明

7、贪心准则在该问题的应用结果是最优的！2022/9/2614贪心算法的基本解题思路1、从问题的某个初始选择出发。2、采用逐步构造策略，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。3、将所有部分解综合起来，得到问题的最终解。2022/9/2615再看一个简单题： （小学数学“希望杯”） 40名学生参加义务植树，任务是：挖树坑，运树苗。这40名学生可分为甲乙丙三类，每类学生的劳动效率如下表所示。如果他们的任务是：挖树坑30个，运树苗不限，那么如何安排人员才能既完成挖树坑的任务，又使树苗运得最多？挖树坑（个/人）运树苗（个/人）人数甲类22015乙类1.210

8、15丙类0.87102022/9/2616贪心策略？挖树坑（个/人）运树苗（个/人）人数甲类22015乙类1.21015丙类0.87102022/9/2617经典问题：事件序列已知N个事件的发生时刻和结束时刻（如下表，表中事件已按结束时刻升序排序）。在时间上没有重叠的一些事件，可以构成一个事件序列，如事件2，8，10。事件序列包含的事件数目，称为该事件序列的长度。请编程找出一个最长的事件序列。事件编号01234567891011发生时刻130325641081515结束时刻34789101214151819202022/9/2618算法分析：用Begini和Endi表示事件i的开始时刻和结束时

9、刻。则原题的要求就是找一个最长的序列a1a2an，满足：Begina1Enda1= BeginanEndan贪心策略？2022/9/2619资源调度假设有许多人在特定的时段需要某个资源（实验室，报告厅），怎么样安排才能满足最多的需求？是不是同一个问题？2022/9/2620贪心策略？每次选取最早结束的事件.为什么？2022/9/2621贪心准则很重要在事件序列的问题，贪心准则是什么？把贪心准则改为：（1）总是选最早的事件（2）总是选时间最少的事件.能否得到最优解？2022/9/2622什么时候有贪心？当我看到它的时候就知道用它贪心准则？ 大胆假设，小心求证2022/9/2623更多的例子202

10、2/9/2624(1) 最少拦截系统Description:某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都达不到前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。怎么办呢，多搞几套拦截系统呗！你说说倒蛮容易，成本呢？成本是个大问题啊。所以俺就到这里来求救了，请帮助计算一下最少需要多少套拦截系统。2022/9/2625Input: 输入若干组数据。每组数据包括：导弹总个数(正整数)，导弹依次飞来的高度（雷达给出的高度数据是不大于300

11、00的正整数，用空格分隔） Output: 对应每组数据，输出拦截所有导弹最少要配备多少套这种导弹拦截系统。 Sample Input: 8 389 207 155 300 299 170 158 65 Sample Output: 22022/9/2626(2)hdOJ1051： wooden stick There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking mac

12、hine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows: (a) The setup time

13、for the first wooden stick is 1 minute. (b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l and weight w if l=l and w大王最弱 田忌最弱PK大王最弱如果 田忌最弱大王最强 田忌最强PK大王最强 （先考虑最强的马发挥最大的作用）如果田忌最强大王最强 田忌最弱PK大王最强 （反正一样是输，避免牺牲最强的马）如果田忌最强=大王最强 田忌最弱PK大王

14、最强（在保证同等输赢的情况下，留住强的马）这样的贪心策略能否保证最优解？2022/9/2639注意到没有贪心往往要结合一定的排序策略老鼠交易 换算的比率大小事件序列 事件结束的时间木板 木板的长&宽赛马 马的速度2022/9/2640(4)1340：矩形移动 平面上有很多个宽度为1长度不等的水平放置的长方形，这些长方形只可在纵坐标方向上自由移动，我们可以将这些长方形经过适当的平移，使得可以用一个最小的矩形区域来覆盖所有这些长方形，同时这些长方形必须满足两两之间都不重叠（若只是边界接触不算重叠）。 2022/9/2641输入：第一行为一个整数n(n=10000)，表示长方形的个数；接下来有n行，

15、每行有三个整数x1,y1,x2(0=x1x2200000,0=y1231)，分别表示一个长方形左下端点的横坐标和纵坐标，以及右下端点的横坐标。 输出：输出最小矩形的面积。 样本输入31 23 33 40 73 17 6 样本输出：12 2022/9/2642分析：水平方向不能移动，意味着 矩形的宽度能否确定？ （x坐标的最小值? 最大值？） y坐标的值有没有关系？怎样让长方形得到有效的邻接，从而减少纵向的长度？2022/9/2643继续分析：问题转换为：需要多少行，各个长方形才不会重叠？资源调度问题？ 什么是资源？水平的一行，在同一行中是不能重叠的。2022/9/2644比较：事件序列： 用一

16、个资源满足尽可能多的需求现在的问题： 用尽可能少的资源（不同行）安排所有的需求（在一行中占据不重叠的位置）类似问题：教室排课2022/9/2645贪心策略：优先选择先出现的长方形进行排列. 如果能排在已有的行，则排在已有的行 否则，新增加一行；2022/9/2646具体做法：按先后次序，让所有的长方形排成行.首先选第一个出现的长方形，排在第一行；接着继续选长方形，只要能接在已有行的后面，就不需要增加行。要多出一行的判断依据？ 前面每一行的最后矩形，都和现在判断的矩形叠加.2022/9/2647细节处理策略（1）X坐标的处理：struct xx int value, flag; flag:0 代

17、表左坐标，flag:1代表右坐标所有的坐标根据value 排序；取第一个x坐标，line=1，nl=1;接下去依次取x坐标,如果flag为1 nr+=1 如果flag为0 nl+=1 如果line+nrnl 则line+； 2022/9/2648（5）HDOJ_1050 Moving TablesSample Input3 4 10 20 30 40 50 60 70 80 2 1 3 2 200 3 10 100 20 80 30 50 Sample Output10 20 30 2022/9/2649算法分析：1、如果在走廊上没有交叉部分，总时间应该是多少？2、影响搬运时间的因素是什么？3

18、、是不是和刚才的矩形移动是相关问题？ 什么是受限的资源？2022/9/2650继续分析：把每个搬运看作一个线段.按先后次序，让所有的线段排成行.首先选第一个线段，排在第一行；接着继续选线段，只要能接在已有行的后面，就不需要增加行；否则多出一行。总行数是不是就是所需的搬运次数？和刚刚的问题是否一样？2022/9/2651换个角度分析：每次都对其中一次安排尽可能多的可重叠搬运，能否得到最优解？考察：交换其中的一些线段，能否减少行数？为什么？2022/9/2652继续分析第2行和第1行肯定有重叠,第3行和第1，2行有公共重叠的地方，.第4行和第1，2，3行有公共重叠的地方因此，. N条line实现的

19、是最大重叠 n的分配那么，能不能减少1条line呢？2022/9/2653经论证的结论：重叠的最大数即为所需资源的最优数量（具体证明略）2022/9/2654HDOJ1050 参考代码，用的就是刚才的结论2022/9/2655HDOJ_1050源码：#include using namespace std; int main() int t,i,j,N,P200; int s,d,temp,k,min; cint; for(i=0;it;i+) for(j=0;jN; for(j=0;jsd; s=(s-1)/2; d=(d-1)/2; if(sd) temp=s; s=d; d=temp;

20、for(k=s;k=d;k+) Pk+; min=-1; for(j=0;jmin) min=Pj; coutmin*10endl; return 0; 2022/9/2656总结： 什么样的问题可以用贪心算法？ 很难定义！当看到它的时候就知道用它2022/9/2657注意：很多贪心类型的题目都不简单，因为所包含的并不是最朴素的贪心，而是需要做一些变化，问题是：如何找到贪心的准则？并不是所有的问题都存在一个有效的贪心算法2022/9/2658本讲重点：(连通网的)最小生成树2022/9/2659 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经

21、费的前提下建立这个通讯网？问题：2022/9/2660 构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。算法二：（克鲁斯卡尔算法）该问题等价于：算法一：（普里姆算法）2022/9/2661MST性质：假设N=V,E是一个连通网， U是顶点集 V的一个非空子集。若（u,v）是一条具有最小权值的边，其中uU, vV-U,则必定存在一棵包含边（u,v）的最小生成树。证明（略）。2022/9/2662 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。普里姆算法的基本思想:2022/9/2663abcdegf例如:195141827168213ae12dcbgf7148531621所得生成树权值和= 14+8+3+5+16+21 = 672022/9/2664 在生成树的