资源预览内容
第1页 / 共32页
第2页 / 共32页
第3页 / 共32页
第4页 / 共32页
第5页 / 共32页
第6页 / 共32页
第7页 / 共32页
第8页 / 共32页
第9页 / 共32页
第10页 / 共32页
亲,该文档总共32页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
ACM程序设计,杭州电子科技大学 刘春英 acmhdu.edu.cn,2018/9/23,2,这学期,,你 了吗?,练习,2018/9/23,3,每周一星(7):,愛詠恒,2018/9/23,4,第八讲,贪心算法 (Greedy Algorithm),2018/9/23,5,导引问题:FatMouse Trade,2018/9/23,6,所谓“贪心算法”是指:,在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。,2018/9/23,7,特别说明:,若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果就是最优解!,2018/9/23,8,用事实说话,2018/9/23,9,一、事件序列问题,已知N个事件的发生时刻和结束时刻(见下表,表中事件已按结束时刻升序排序)。一些在时间上没有重叠的事件,可以构成一个事件序列,如事件 2,8,10。事件序列包含的事件数目,称为该事件序列的长度。请编程找出一个最长的事件序列。,2018/9/23,10,算法分析:,不妨用Begini和Endi表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1a2an,满足: Begina1Enda1= BeginanEndan,可以证明,如果在可能的事件a1a2an中选取在时间上不重叠的最长序列,那么一定存在一个包含a1(结束最早)的最长序列。 (证明:略),2018/9/23,11,思考:,请谈谈自己的解题思路,2018/9/23,12,思考题,2037 今年暑假不AC,2018/9/23,13,二、区间覆盖问题,用i来表示x轴上坐标为i-1,i的区间(长度为1),并给出M(1=M=200)个不同的整数,表示M个这样的区间。现在让你画几条线段覆盖住所有的区间,条件是:每条线段可以任意长,但是要求所画线段之和最小,并且线段的数目不超过N(1=N=M,那么显然用M条长度为1的线段可以覆盖住所有的区间,所求的线段总长为M。 如果N=1,那么显然所需线段总长为: 如果N=2,相当于N=1的情况下从某处断开(从哪儿断开呢?)。 如果N=k呢?,2018/9/23,15,三、HDOJ_1050 Moving Tables,Sample Input 3 4 10 20 30 40 50 60 70 80 2 1 3 2 200 3 10 100 20 80 30 50,Sample Output 10 20 30,2018/9/23,16,算法分析:,1、如果没有交叉,总时间应该是多少? 2、影响搬运时间的因素是什么? 3、如果每趟处理都包含最大重叠,处理后的效果是什么? 4、得出什么结论?,2018/9/23,17,附:参考源码(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=s; s=d; d=temp; for(k=s;kmin) min=Pj; coutmin*10endl; return 0; ,2018/9/23,18,贪心算法的基本步骤,1、从问题的某个初始解出发。 2、采用循环语句,当可以向求解目标前进一步时,就根据局部最优策略,得到一个部分解,缩小问题的范围或规模。 3、将所有部分解综合起来,得到问题的最终解。,2018/9/23,19,贪心算法都很简单吗?,看一道难一些的。 (2004年上海赛区:正式赛是简单题),2018/9/23,20,ACM-ICPC Asia Regional, 2004, Shanghai,Tian JiThe Horse Racing,2018/9/23,21,示意图:,2018/9/23,22,谈谈自己的想法吧,2018/9/23,23,Case 1:,King: 200 180 160 Tianji: 190 170 150,2018/9/23,24,Case 2:,King: 200 180 160 Tianji: 180 170 150,2018/9/23,25,Case 3:,King: 200 180 160 Tianji: 180 155 150,2018/9/23,26,总体的思路是什么?,2018/9/23,27,提醒:,很多贪心类型的题目都象本题一样,不是最朴素的贪心,而是需要做一些变化,对于我们,关键是找到贪心的本质!,2018/9/23,28,最后一个思考题,Any questions?,2018/9/23,30,相关练习,另外还有 1203、 1204、 1239 1579、 1730、 2285,DIY:ACM程序设计课后练习(8)刘春英,2018/9/23,31,Welcome to HDOJ,Thank You ,2018/9/23,32,每周一星(7):,木雪空亦,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号