《ACM课件1lecture06贪心算法》由会员分享，可在线阅读，更多相关《ACM课件1lecture06贪心算法（44页珍藏版）》请在金锄头文库上搜索。
1、2019/6/12,1,ACM 程序设计,信息学院计算机应用系 余腊生,2019/6/12,2,调课三周 (11/6,11/13,11/20),2019/6/12,3,今天，,你 了吗？,AC,2019/6/12,4,每周一星（5）：,枫冰叶子,2019/6/12,5,第六讲,贪心算法 （Greedy Algorithm）,2019/6/12,6,还记得hdoj_1009吗？,FatMouse Trade,2019/6/12,7,所谓“贪心算法”是指：,在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证
2、明）。,2019/6/12,8,特别说明：,若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！,2019/6/12,9,用事实说话,2019/6/12,10,实 例 分 析,2019/6/12,11,一、事件序列问题,已知N个事件的发生时刻和结束时刻（见下表，表中事件已按结束时刻升序排序）。一些在时间上没有重叠的事件，可以构成一个事件序列，如事件 2，8，10。事件序列包含的事件数目，称为该事件序列的长度。请编程找出一个最长的事件序列。,2019/6/12,12,算法分析：,不妨用Begini和Endi表示事件i的开始时刻和结束时刻。则原题的要求就是找一个
3、最长的序列a1a2an，满足： Begina1Enda1= BeginanEndan,可以证明，如果在可能的事件a1a2an中选取在时间上不重叠的最长序列，那么一定存在一个包含a1（结束最早）的最长序列。 （证明：略）,2019/6/12,13,思考：,请谈谈自己的解题思路,2019/6/12,14,练习题目： 2037 今年暑假不AC,2019/6/12,15,二、区间覆盖问题,用i来表示x轴上坐标为i-1,i的区间（长度为1），并给出M(1=M=200)个不同的整数，表示M个这样的区间。现在让你画几条线段覆盖住所有的区间，条件是：每条线段可以任意长，但是要求所画线段之和最小，并且线段的数目
4、不超过N(1=N=50)。 例如：M=5个整数1、3、4、8和11表示区间，要求所用线段不超过N=3条 0 1 2 3 4 5 6 7 8 9 10 11,2019/6/12,16,算法分析：,如果N=M，那么显然用M条长度为1的线段可以覆盖住所有的区间，所求的线段总长为M。 如果N=1，那么显然所需线段总长为： 如果N=2，相当于N=1的情况下从某处断开（从哪儿断开呢？）。 如果N=k呢？,2019/6/12,17,三、HDOJ_1050 Moving Tables,题目链接 Sample Input 3 4 10 20 30 40 50 60 70 80 2 1 3 2 200 3 10
5、100 20 80 30 50,Sample Output 10 20 30,2019/6/12,18,算法分析：,1、如果没有交叉，总时间应该是多少？ 2、影响搬运时间的因素是什么？ 3、如果每趟处理都包含最大重叠，处理后 的效果是什么？ 4、得出什么结论？,2019/6/12,19,HDOJ_1050源码：,#include using namespace std; int main() int t,i,j,N,P200; int s,d,temp,k,min; cint; for(i=0;iN; for(j=0;jsd; s=(s-1)/2; d=(d-1)/2;,if(sd) temp
6、=s; s=d; d=temp; for(k=s;kmin) min=Pj; coutmin*10endl; return 0; ,2019/6/12,20,贪心算法的基本步骤,1、从问题的某个初始解出发。 2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。 3、将所有部分解综合起来，得到问题的最终解。,2019/6/12,21,贪心算法都很简单吗？,看一道难一些的。 （2004年上海赛区试题：当时算是简单题）,2019/6/12,22,ACM-ICPC Asia Regional, 2004, Shanghai,Problem H Tia
7、n JiThe Horse Racing,2019/6/12,23,示意图：,2019/6/12,24,谈谈自己的想法,2019/6/12,25,Case 1:,King: 200 180 160 Tianji: 190 170 150,2019/6/12,26,Case 2:,King: 200 180 160 Tianji: 180 170 150,2019/6/12,27,Case 3:,King: 200 180 160 Tianji: 180 155 150,2019/6/12,28,总体的思路是什么？,2019/6/12,29,提醒：,很多贪心类型的题目都象本题一样，不是最朴素的贪
8、心，而是需要做一些变化，对于我们，关键是找到贪心的本质！,2019/6/12,30,本讲重点： (连通网的)最小生成树,2019/6/12,31,假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？,问题：,2019/6/12,32,构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。,算法二：（克鲁斯卡尔算法）,该问题等价于：,算法一：（普里姆算法）,2019/6/12,33,MST性质：,假设N=V,E是一个连通网， U是顶点集 V的一个非空子集。若（u,v）是一条
9、具有最小权值的边，其中uU, vV-U,则必定存在一棵包含边（u,v）的最小生成树。 证明（略）。,2019/6/12,34,取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。,普里姆算法的基本思想:,2019/6/12,35,a,b,c,d,e,g,f,例如:,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,所得生
10、成树权值和,= 14+8+3+5+16+21 = 67,2019/6/12,36,在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,一般情况下所添加的顶点应满足下列条件:,2019/6/12,37,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,7,a,a,a,19,14,18,14,例如:,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,2019/6/12,38,具体做法: 先构造一个只
11、含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。,考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,克鲁斯卡尔算法的基本思想：,2019/6/12,39,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,例如:,7,12,18,19,2019/6/12,40,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n2),O(eloge),稠密图,稀疏图,算法名,适应范
12、围,比较两种算法,2019/6/12,41,请务必写出自己的模版！,2019/6/12,42,再次提醒: 调课三周 (11/6,11/13,11/20),2019/6/12,43,附：贪心算法练习题：,1045 Fire Net 1050 Moving Tables 1051 Wooden Sticks 1052 Tian Ji - The Horse Racing 1053 Entropy 1054 Strategic Game 2037今年暑假不AC 1076、1203、 1204、 1239、1579、 1730、 2285 最小生成树：1102、1301、1162、1233,2019/6/12,44,ACM, 天天见！,
