今天， AC 你 了吗？ 2019/4/19.

Presentation on theme: "今天， AC 你 了吗？ 2019/4/19."— Presentation transcript:

1 今天， AC 你 了吗？ 2019/4/19

2 第七讲 贪心算法 （Greedy Algorithm） 2019/4/19

3 还记得hdoj_1009吗？ FatMouse' Trade 2019/4/19

4 所谓“贪心算法”是指： 在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。 2019/4/19

5 特别说明： 若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！！ 2019/4/19

6 用事实说话—— 2019/4/19

7 实 例 分 析 2019/4/19

8 一、事件序列问题 已知N个事件的发生时刻和结束时刻（见下表，表中事件已按结束时刻升序排序）。一些在时间上没有重叠的事件，可以构成一个事件序列，如事件 {2，8，10}。事件序列包含的事件数目，称为该事件序列的长度。请编程找出一个最长的事件序列。 事件编号 1 2 3 4 5 6 7 8 9 10 11 发生时刻 15 结束时刻 12 14 18 19 20 2019/4/19

9 算法分析： 不妨用Begin[i]和End[i]表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1<a2<…<an，满足： Begin[a1]<End[a1]<=…<= Begin[an]<End[an] 可以证明，如果在可能的事件a1<a2<…<an中选取在时间上不重叠的最长序列，那么一定存在一个包含a1（结束最早）的最长序列。 （证明：略） 2019/4/19

10 思考： 请谈谈自己的解题思路 2019/4/19

11 练习题目： 今年暑假不AC 2019/4/19

12 二、区间覆盖问题 用i来表示x轴上坐标为[i-1,i]的区间（长度为1），并给出M(1=<M=<200)个不同的整数，表示M个这样的区间。现在让你画几条线段覆盖住所有的区间，条件是：每条线段可以任意长，但是要求所画线段之和最小，并且线段的数目不超过N(1=<N=<50)。 例如：M=5个整数1、3、4、8和11表示区间，要求所用线段不超过N=3条 2019/4/19

13 算法分析： 如果N>=M，那么显然用M条长度为1的线段可以覆盖住所有的区间，所求的线段总长为M。
如果N=2，相当于N=1的情况下从某处断开（从哪儿断开呢？）。 如果N=k呢？ 2019/4/19

14 三、HDOJ_1050 Moving Tables 10 20 30 Sample Output 题目链接 Sample Input
Sample Output 2019/4/19

15 算法分析： 1、如果没有交叉，总时间应该是多少？ 2、影响搬运时间的因素是什么？ 3、如果每趟处理都包含最大重叠，处理后 的效果是什么？
3、如果每趟处理都包含最大重叠，处理后 的效果是什么？ 4、得出什么结论？ 2019/4/19

16 HDOJ_1050源码： if(s>d) { temp=s; s=d; #include <iostream>
for(k=s;k<=d;k++) P[k]++; } min=-1; for(j=0;j<200;j++) if(P[j]>min) min=P[j]; cout<<min*10<<endl; return 0; #include <iostream> using namespace std; int main() { int t,i,j,N,P[200]; int s,d,temp,k,min; cin>>t; for(i=0;i<t;i++) { for(j=0;j<200;j++) P[j]=0; cin>>N; for(j=0;j<N;j++) cin>>s>>d; s=(s-1)/2; d=(d-1)/2; 2019/4/19

17 贪心算法的基本步骤 1、从问题的某个初始解出发。
2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。 3、将所有部分解综合起来，得到问题的最终解。 2019/4/19

18 贪心算法都很简单吗？ 看一道难一些的。 （2004年上海赛区试题：当时算是简单题） 2019/4/19

19 ACM-ICPC Asia Regional, 2004, Shanghai
Problem H Tian Ji—The Horse Racing 2019/4/19

20 示意图： 92 83 71 74 87 95 -200 92 83 71 74 87 95 -200 +200 92 83 71 74 87 95 2019/4/19

21 谈谈自己的想法—— 2019/4/19

22 Case 1: King: Tianji: 2019/4/19

23 Case 2: King: Tianji: 2019/4/19

24 Case 3: King: Tianji: 2019/4/19

25 总体的思路是什么？ 2019/4/19

26 提醒： 很多贪心类型的题目都象本题一样，不是最朴素的贪心，而是需要做一些变化，对于我们，关键是找到贪心的本质！ 2019/4/19

27 本讲重点： (连通网的)最小生成树 2019/4/19

28 问题： 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？
2019/4/19

29 算法一：（普里姆算法） 算法二：（克鲁斯卡尔算法） 该问题等价于：
构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。 算法一：（普里姆算法） 算法二：（克鲁斯卡尔算法） 2019/4/19

30 MST性质： 假设N={V,{E}}是一个连通网， U是顶点集 V的一个非空子集。若（u,v）是一条具有最小权值的边，其中u∈U, v∈V-U,则必定存在一棵包含边（u,v）的最小生成树。 证明（略）。 2019/4/19

31 普里姆算法的基本思想: 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。 2019/4/19

32 例如: a a b b c c e e g g d d f f 所得生成树权值和 = 14+8+3+5+16+21 = 67 19 5 5
12 14 14 c c 7 18 e e 8 8 16 16 3 3 g g d d 27 21 21 f f 所得生成树权值和 = = 67 2019/4/19

33 一般情况下所添加的顶点应满足下列条件: 在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。 2019/4/19

34 例如: a a b b c c e e d d g f e c d a d e a d e a 7 5 12 19 5 3 3 8 8 14
18 8 3 e e 16 d d g 21 27 f e c d a d e a d e a 7 5 12 19 5 3 3 8 8 14 14 21 18 16 2019/4/19

35 克鲁斯卡尔算法的基本思想： 考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。
具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。 2019/4/19

36 例如: 19 19 a a b b 5 5 12 12 14 14 c c 7 7 18 18 e e 16 16 8 8 3 3 g g d d 27 21 21 f f 2019/4/19

37 比较两种算法 克鲁斯卡尔算法 算法名 普里姆算法 时间复杂度 O(n2) O(eloge) 适应范围 稠密图 稀疏图 2019/4/19

38 请务必写出自己的模版！ 2019/4/19

39 附：贪心算法练习题： 最小生成树：1102、1301、1162、1233 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/4/19

40 ACM, 天天见！ 2019/4/19