贪心算法 ppt课件

1、ACM程序设计程序设计杭州电子科技大学 刘春英这学期，这学期，他他 了吗？了吗？练习每周一星每周一星8：qzx 第九讲第九讲贪婪算法贪婪算法Greedy Algorithm导引问题：导引问题：FatMouse TradeFatMouse Trade所谓所谓“贪婪算法是指：贪婪算法是指：在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以思索，它所作出的仅仅是在某种意义上的部分最优解能否是全局最优，需求证明。特别阐明：特别阐明：假设要用贪婪算法求解某问题的整体最优解，必需首先证明贪婪思想在该问题的运用结果就是最优解！用现实说话用现实说话一、事件序列问题一、

2、事件序列问题 知N个事件的发生时辰和终了时辰见下表，表中事件已按终了时辰升序排序。一些在时间上没有重叠的事件，可以构成一个事件序列，如事件2，8，10。事件序列包含的事件数目，称为该事件序列的长度。请编程找出一个最长的事件序列。事件编号 0 1 2 3 45678910 11发生时刻 1 3 0 3 2564 10 815 15结束时刻 3 4 7 8 9 10 12 14 15 18 19 20算法分析：算法分析：n无妨用Begini和Endi表示事件i的开场时辰和终了时辰。那么原题的要求就是找一个最长的序列a1a2an，满足：nBegina1Enda1= BeginanEndan可以证明，

3、假设在能够的事件a1a2an中选取在时间上不重叠的最长序列，那么一定存在一个包含a1终了最早的最长序列。证明：略思索：思索：n请谈谈本人的解题思绪思索题思索题n2037 2037 今年暑假不今年暑假不ACAC 二、区间覆盖问题二、区间覆盖问题 用i来表示x轴上坐标为i-1,i的区间长度为1，并给出M(1=M=200)个不同的整数，表示M个这样的区间。如今让他画几条线段覆盖住一切的区间，条件是：每条线段可以恣意长，但是要求所画线段之和最小，并且线段的数目不超越N(1=N=M，那么显然用M条长度为1的线段可以覆盖住一切的区间，所求的线段总长为M。n假设N=1，那么显然所需线段总长为：n假设N=2，

4、相当于N=1的情况下从某处断开从哪儿断开呢？。n假设N=k呢？三、三、HDOJ_1050 Moving TablesSample Input3 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 算法分析：算法分析：1、假设没有交叉，总时间应该是多少？2、影响搬运时间的要素是什么？3、假设每趟处置都包含最大重叠，处置后的效果是什么？4、得出什么结论？附附: :参考源码参考源码(HDOJ-1050)(HDOJ-1050)#include using namespace std; int

5、 main() int t,i,j,N,P200; int s,d,temp,k,min; cint; for(i=0;it;i+) for(j=0;jN; for(j=0;jsd; s=(s-1)/2; d=(d-1)/2; if(sd) temp=s; s=d; d=temp; for(k=s;k=d;k+) Pk+; min=-1; for(j=0;jmin) min=Pj; coutmin*10endl; return 0; 贪婪算法的根本步骤贪婪算法的根本步骤 1、从问题的某个初始解出发。2、采用循环语句，当可以向求解目的前进一步时，就根据部分最优战略，得到一个部分解，减少问题的范围

6、或规模。3、将一切部分解综合起来，得到问题的最终解。贪婪算法都很简单吗？贪婪算法都很简单吗？看一道难一些的。2019年上海赛区：正式赛是简单题ACM-ICPC Asia Regional, 2019, ShanghaiTian JiThe Horse RacingTian JiThe Horse Racing表示图：表示图：928371748795928371748795-200-200-200928371748795-200+200+200谈谈本人的想法吧谈谈本人的想法吧Case 1:Case 1:King: 200 180 160King: 200 180 160Tianji: 190 1

7、70 150Tianji: 190 170 150Case 2:Case 2:King: 200 180 160King: 200 180 160Tianji: 180 170 150Tianji: 180 170 150Case 3:Case 3:King: 200 180 160King: 200 180 160Tianji: 180 155 Tianji: 180 155 150150总体的思绪是什么？总体的思绪是什么？提示：提示：很多贪婪类型的标题都象此题一样，不是最朴素的贪婪，而是需求做一些变化，对于我们，关键是找到贪婪的本质！最后一个思索题最后一个思索题Any Any questions?questions?