《贪心算法课件.ppt》由会员分享，可在线阅读，更多相关《贪心算法课件.ppt（48页珍藏版）》请在三一文库上搜索。
1、天津大学ACM讲座贪心算法及其应用,05级 QQ：591294402 Email：,主要内容,贪心算法简介 贪心算法应用 最优装载问题 单源最短路径问题 区间问题 哈夫曼编码 练习题目,贪心算法简介,贪心算法是一个解决最优子结构问题的算法。顾名思义，贪心算法总是做出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。,贪心算法简介,虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。例如，图的单源最短路径问题，最小生成树问题等。 在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。,应用1最优
2、装载,问题： 有一批集装箱要装上一艘载重量为 c 的轮船，其中集装箱 i 的重量为 ,在装载体积不受限制的情况下，应如何装载才能把尽可能多的集装箱装上轮船？,简单！,应用1最优装载,本题可形式化描述为 max 其中，变量 = 0表示不装入集装箱i ， =1表示装入集装箱i,应用1最优装载,本例显然可用贪心算法求解。 将集装箱按重量由小到大排序，重量最轻者先装，每一次都挑选剩余集装箱中最轻的装入，直到不能装入为止。得到本问题的一个最优解。 实现代码如下：,应用1最优装载,#include #include using namespace std; const int N = 10002; str
3、uct node int id; int weight; aN; bool xN; int cmp( node a, node b ) return a.weight b.weight; /定义的比较函数cmp， /用于排序,int main() int i,c,n,nc; while (scanf(%d%d, ,应用1最优装载,memset (x, 0, sizeof( x );/先清零 for (i = nc = 0; i n ; i+)/nc为当前装入轮船的重量 if (nc + a i .weight = c) nc += a i .weight; x a i .id = 1; for
4、 (i = 0; i n; i+)/输出结果 if (x i = 1) printf( %dn, i ); return 0; ,应用2单源最短路径,问题描述 已知图G=(V,E)，我们希望找出从某个给定源顶点sV到每个顶点vV的最短路径。 Dijkstra算法 每次在剩余的点中挑选距离源点s最近的点。直到找到目的顶点d。,应用2-Dijkstra(G,w,s),initialize-single-sorce(G,s) S Q V while(Q != ) do u min(Q) S Su for 每个与u相邻的定点v relax(u,v,w) 因为Dijkstra算法总是在V-S中选择“最轻
5、”或“最近”的定点插入集合S中，所以我们说它使用了贪心策略。,应用2单源最短路径,Dijkstra是应用贪心算法设计策略的一个典型例子。源点到定点u的最短路为distu。它这种贪心选择为什么能导致最优解呢？ 简单证明（反证法） 假设存在一条从源点s到u且长度比distu更短的路，设这条路经过在S之外的定点x最后到达u,则 distx = 0,故而得到 distx distu,而这样的话x将会先于u被选入S集合内。这与假设条件矛盾。,应用2单源最短路径,注：单源最短路径的dijkstra算法、最小生成树的Prim算法和Kruskal算法都可以看做是应用贪心算法设计策略的典型例子。11月2日的讲座
6、已经讲过这些了，这里不再赘述。 这里只举一个简单例子：TOJ 2976 题目描述：要寻找从商店到赛场的最短的路线。 输入：每组数据两个整数N、M（N=100，M=10000），N表示大街上有几个路口，1是商店，N是赛场，M表示有几条路。N=M=0表示输入结束。接下来M行，每行3个整数A，B，C（1=A,B=N,1=C=1000）,表示在路口A与B之间有一条路，工作人员需C分钟走过这条路。 输出：对每组输入，输出一行，表示工作人员从商店走到赛场的最短时间,应用2单源最短路径,样例输入： 2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0,样例输出： 3 2,裸最短路问题！,应
7、用2单源最短路径,直接运用Dijkstra算法即可。,应用3区间问题,在比赛中，有很多问题最终都能转化为区间问题：例如从若干个区间中选出一些满足一定条件的区间、将各个区间分配到一些资源中、或者将一些区间以某种顺序放置等。如活动安排问题、机器调度问题等等。 这类问题变化繁多，解法各异。下面介绍几种常见模型。,区间问题1.最大区间调度问题,数轴上有n个区间，选出最多的区间，使得这些区间不互相重叠。 算法： 按右端点坐标排序 依次选择所有能选的区间,区间问题1.最大区间调度问题,证明 例题：TOJ 2867 某人想要参加一系列活动，已知每个活动的开始时间和持续时间，问他最多能参加几个活动。,Samp
8、le Input 5 0 3 5 10 9 2 3 4 2 2 0 Sample Output 3,区间问题1.最大区间调度问题,分析：本题已知每个活动的起始时间和持续时间，由此可得到活动的起始时间和终止时间，即各区间的两个端点。显然，这是最大区间调度问题。 应用上面所讲的贪心算法即可求解。,区间问题2.多个资源的调度问题,有n个区间和无限多的资源，每个资源上的区间之间不互相重叠。将每个区间都分配到某个资源中，使用到的资源数量最小。,定义区间集合深度d为包含任意一点的区间数量的最大值 至少需要d个资源 算法： 计算出d 按左端点坐标排序 依次将区间任意地分配到d个资源中,可以证明每个区间都能分
9、配到资源,区间问题2.多个资源的调度问题,关键： 区间深度d如何计算？ d的计算方法： 将每个区间拆成两个事件点，按坐标从小到大排序，顺序处理每个区间。记录一个值，表示当前点被包含次数。每次遇到区间的左端点就+1，遇到右端点就-1。的值就是在该过程中的最大值。注意两个相同坐标不同类型的事件点的位置关系和区间是否能在端点处重叠有关，这在排序过程中应该注意。,区间问题2.多个资源的调度问题,例：TOJ 2894 Meetings（07年保研复试题） 题目描述： 给出会议的起止时间（即给出了各个区间），问安排这些会议最少需要多少个会议室?（一个会议结束的时刻，另一个会议可以马上开始） 分析：会议室多
10、个资源；会议区间；将每个区间都分配给某个资源，使用到的资源数量最小，即要求解的是区间深度d。,注意：前面提到，加1与减1的先后顺序与每个区间在端点处可否重叠有关。对本题而言，显然要求可以重叠，故应该先减1再加1。 算法主体部分可参加下页代码。 其中，a 和b 分别存放各区间的左端点和右端点。j1和j2分别是数组a 、b 的下标。r是贯穿整个for循环的变量，遇到区间右端点则加1，遇到区间左端点则减1。result 为for循环过程中r的最大值，即区间深度d。,TOJ 2894,TOJ 2894,MAX = MIN = 0; for (i = 0; i a i ) MIN = a i ; sor
11、t (a, a + n); /对左端点进行排序 sort (b, b + n); /对右端点进行排序 j1 = j2 = 0; result = 0; r = 0;,TOJ 2894,for (i = MIN; i = n) i = a j1 ; else if (j2 = n) i = b j2 ; else break; printf( “%dn”, result ); /最后输出结果,区间问题3.有最终期限的区间调度问题,有n个长度固定、但位置可变的区间，将它们全部放置在0,+)上。每个区间有两个已知参数：长度ti和最终期限di，设fi为其右端点坐标。定义 放置所有区间，使它们不互相重叠
12、且最大延迟L最小。,算法： 按最终期限排序 顺序安排各区间,例题：Europe - Southeastern 2007 Problem D 一个银行家收到了N个贷款申请，每个贷款最晚都要在 前完成，利润为 ，每个贷款均需要一个单位时间来处理，银行在同一时间内最多可接受L个贷款， 问如何安排能使获得利润最大？ 分析： 将每个贷款申请看作一个单位长度、位置可变且带权的区间，则题目转化为选出一些区间，将它们不互相重叠地放在L个资源上，使利润最大，且区间的左端点不得超过 。可用贪心算法解决该问题。,区间问题3.有最终期限的区间调度问题,区间问题3.有最终期限的区间调度问题,算法： 将这些区间按照权值从
13、大到小排序，顺序处理每个区间。设 由于区间都是单位长度的，我们可以用一维数组 来记录当前的情况,表示 被覆盖次数，根据题意有 处理第i个区间时，若可以选择该区间， （即 ），则将该区间放置到一个i最大的一个位置，即 ，否则就不选择该区间。,区间问题3.有最终期限的区间调度问题,与上例相似的一道题：TOJ 1681 唯一的一点不同是toj 1681同一时刻只能处理一件产品，即上页算法中的L是1。因此toj 1681要简单一些。大家回去可以按照上述算法做一做。,参见如下部分代码： sort (a, a + n, cmp); memset (s, -1, sizeof(s); for (i = 0;
14、 i = 0; j-) if (s j = -1) s j = i; break; ,区间问题4.最小区间覆盖问题,有n个区间，选择尽量少的区间，使得这些区间完全覆盖某线段s,t。 算法： 按左端点坐标排序 每次选择覆盖点s的区间中右端点坐标最大的一个，并更新s 直到所选区间已包含t,S,T,Max,区间问题5.区间和点的有关问题,有n个区间，m个点。若某区间包含了某点，则构成一对匹配关系。选出最多的区间和相同数量的点，使对应的区间和点构成匹配关系。,二分图匹配？,太慢,算法：,所有点按坐标排序 选取包含该点且右端点坐标最小的区间,时间复杂度O(nm),优化,按区间左端点排序，得到有序表 维护
15、二叉堆，以区间右端点为关键字 所有点按坐标从小到大依次处理,维护二叉堆： 插入左端点小于等于该点坐标的区间 删除右端点小于该点坐标的区间 取出右端点坐标最小的与该点匹配并删除,有序表,二叉堆,时间复杂度O(nlogn+mlogm),区间问题总结,有序性大多数问题都要先排序，经常要用到结构体、写比较函数。排序的时候要选好排序的关键字。 算法的选择与设计 优化数据结构的选择：有时候为了避免超时，要进行适当优化，比如用二叉堆来维护，等等。,应用4哈夫曼编码,哈夫曼编码是用于数据文件压缩的一个十分有效的编码方法。其压缩率在20%90%之间。哈夫曼编码是可变字长编码(VLC)的一种。 Huffman于1
16、952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 哈夫曼树（即最优二叉树），带权路径长度最小的二叉树。,应用4哈夫曼编码,以自底向上的方式构造最优二叉树T。以|C|个叶子结点开始，执行|C|-1次的“合并”运算后产生最终所要求的树T，每次找到两个频度最低的对象进行合并，合并的结果是一个新对象，其频度为被合并的两个对象的频度之和。最终使得 （即树T的代价）最小。其中， f(c)c出现的频度； c的深度。,应用4哈夫曼编码,例：共有6个字母，各自频度如下： f:5 e:9 c:12 b:13 d:16 a:45
17、,应用4哈夫曼编码,应用4哈夫曼编码,例题：TOJ 2849 题目大意：把一根长木板切成要求的n段，每段长度Li已知，共需切割n-1次。每次切割的花销与切割之前木板长度相等。求最小的花销。n=20000; Li=50000. Sample Input Sample Output 3 34 8 5 8,分析,应用4哈夫曼编码TOJ 2849,尝试不同的贪心策略： 对于Sample，三段8，5，8，答案34。 34 = 21 + 13 = （8 + 8 + 5）+（8 + 5） 猜想贪心策略1：按照长度排序，每次切割下剩余部分中最长的？这种方法是否可行？ 不可行！ 原因：反例：输入：5、6、8、9
18、，按上面的猜想策略做，9、8、6、5，每次切割前总长度分别是28、19、11，总花销=28+19+11=58.而实际上，这个例子的最优解应该是 56 = 28 + 11 + 17，也就是说第一次切成11和17两段，第二次把11切成5和6两段，第三次把17切成8和9两段。,应用4哈夫曼编码TOJ 2849,注意数据范围。可能超int，故而用long long。 参见如下代码： #include #include using namespace std; const int N = 20002; long long heap N ; int hcmp( int a, int b ) return
19、a b;/小顶堆的比较函数 ,应用4哈夫曼编码,int main() long long i, n, len, Length, TotalLength; while (scanf( %lld, /堆的大小,应用4哈夫曼编码,for (i = 0; i n - 1; i+) Length = heap 0 ; pop_heap (heap, heap + len, hcmp);/默认的是大顶堆 ，此处加上hcmp为小顶堆 len-; Length += heap 0 ; pop_heap (heap, heap + len, hcmp); len-; TotalLength += Length;
20、 heap len+ = Length; push_heap (heap, heap + len, hcmp); printf(%lldn, TotalLength); return 0; ,贪心算法总结,本次课件中介绍集中类型是贪心算法的典型应用，大家尽量掌握。 贪心题目类型多样，很多情况下要具体情况具体分析。 猜测一种贪心策略，证明。不要想当然，多举例验证。 贪心的代码实现往往比较简单。,练习题目,TOJ 2867 TOJ 2894 TOJ 1681 TOJ 2849 TOJ 1115,POJ 1789 POJ 2485 POJ 1258 POJ 3026 POJ 2586,The End,_,谢谢,