acm算法_贪心算法
ACM 程序设计计算机学院 刘春英*1调课三周 (11/6,11/13,11/20)Date2今天，你 了吗？ACDate3每周一星（5）：枫冰叶子 Date4第六讲贪心算法 （Greedy Algorithm）Date5还记得hdoj_1009吗？FatMouse' TradeDate6所谓“贪心算法”是指：在对问题求解时，总是作出在当前看来 是最好的选择。也就是说，不从整体上 加以考虑，它所作出的仅仅是在某种意 义上的局部最优解（是否是全局最优， 需要证明）。Date7特别说明：若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！Date8用事实说话Date9实 例 分 析Date10一、事件序列问题 已知N个事件的发生时刻和结束时刻（见下表， 表中事件已按结束时刻升序排序）。一些在时间上 没有重叠的事件，可以构成一个事件序列，如事件 2，8，10。事件序列包含的事件数目，称为该事 件序列的长度。请编程找出一个最长的事件序列。事件编号01 2 3 4567891011发生时刻 13 0 3 25641081515结束时刻 34 7 8 9 10 12 14 15 18 1920Date11算法分析：l不妨用Begini和Endi表示事件i的开始时 刻和结束时刻。则原题的要求就是找一个 最长的序列a1=M，那么显然用M条长度为1的 线段可以覆盖住所有的区间，所求的线 段总长为M。l如果N=1，那么显然所需线段总长为：l如果N=2，相当于N=1的情况下从某处断 开（从哪儿断开呢？）。l如果N=k呢？Date16三、HDOJ_1050 Moving Tablesl题目链接 Sample 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 Date17算法分析：1、如果没有交叉，总时间应该是多少？ 2、影响搬运时间的因素是什么？3、如果每趟处理都包含最大重叠，处理后 的效果是什么？ 4、得出什么结论？Date18HDOJ_1050源码：#include using namespace std; int main() int t,i,j,N,P200;int s,d,temp,k,min; cin>>t; for(i=0;i>N; for(j=0;j>s>>d; s=(s-1)/2; d=(d-1)/2; if(s>d) temp=s; s=d; d=temp; for(k=s;kmin) min=Pj; cout<<min*10<<endl; return 0; Date19贪心算法的基本步骤 1、从问题的某个初始解出发。2、采用循环语句，当可以向求解目标前 进一步时，就根据局部最优策略，得到 一个部分解，缩小问题的范围或规模。3、将所有部分解综合起来，得到问题的 最终解。Date20贪心算法都很简单吗？看一道难一些的。 （2004年上海赛区试题：当时算是简单 题）Date21ACM-ICPC Asia Regional, 2004, ShanghaiProblem H Tian JiThe Horse RacingDate22示意图：928371748795928371748795-200-200-200928371748795-200+200+200Date23谈谈自己的 想法Date24Case 1:King: 200 180 160 Tianji: 190 170 150Date25Case 2:King: 200 180 160 Tianji: 180 170 150Date26Case 3:King: 200 180 160 Tianji: 180 155 150Date27总体的思路 是什么？Date28提醒：很多贪心类型的题目都象本 题一样，不是最朴素的贪心 ，而是需要做一些变化，对 于我们，关键是找到贪心的 本质！Date29本讲重点：(连通网的)最小生成树Date30假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？问题：Date31构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成 回路），使“权值之和”为最小。算法二：（克鲁斯卡尔算法）该问题等价于：算法一：（普里姆算法）Date32MST性质：l假设N=V,E是一个连通网， U是顶 点集 V的一个非空子集。若（u,v）是 一条具有最小权值的边，其中uU, vV-U,则必定存在一棵包含边（u,v） 的最小生成树。l证明（略）。Date33取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。普里姆算法的基本思想:Date34abcdegf例如:195 14 1827168213ae12dcbgf7148531621 所得生成树权值和= 14+8+3+5+16+21 = 67Date35在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的 顶点集 U 和尚未落在生成树上的顶点集 V-U ，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。一般情况下所添加的顶点应满足下列 条件:Date36ab cde g f19514 1827168213ae12dcb7aaa 19141814例如:e12ee8168d3dd7213c5 5Date37具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添 加不使SG 中产生回路，则在 SG 上加上这 条边，如此重复，直至加上 n-1 条边为止。考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：Date38abcdegf195 14 1827168213ae12dcbgf7148531621例如:7121819Date39普里姆算法克鲁斯卡尔算法时间复杂度O(n2)O(eloge)稠密图稀疏图算法名适应范围比较两种算法Date40请务必写出自己的模版！Date41再次提醒:调课三周 (11/6,11/13,11/20)Date42附：贪心算法练习题：l1045 Fire Netl1050 Moving Tablesl1051 Wooden Sticks l1052 Tian Ji - The Horse Racingl1053 Entropyl1054 Strategic Gamel2037今年暑假不AC l1076、1203、 1204、 1239、1579、 1730、 2285l最小生成树：1102、1301、1162、1233Date43ACM, 天天见！ Date44
