ACM算法_貪心算法.ppt

《ACM算法_貪心算法.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、ACM程序設(shè)計(jì)計(jì)算機(jī)學(xué)院劉春英9/17/20211調(diào)課三周(11/6,11/13,11/20)9/17/20212今天，你了嗎？AC9/17/20213每周一星（5）：楓冰葉子9/17/20214第六講貪心算法（GreedyAlgorithm）9/17/20215還記得hdoj_1009嗎？FatMouse'Trade9/17/20216所謂“貪心算法”是指：在對(duì)問題求解時(shí)，總是作出在當(dāng)前看來是最好的選擇。也就是說，不從整體上加以考慮，它所作出的僅僅是在某種意義上的局部最優(yōu)解（是否是全局最優(yōu)，需要證明）。9/17/20217特別說明：若要用貪心算法求解某問題的整體最優(yōu)解，必須首先證明貪心思想

2、在該問題的應(yīng)用結(jié)果就是最優(yōu)解！！9/17/20218用事實(shí)說話——9/17/20219實(shí)例分析9/17/202110一、事件序列問題已知N個(gè)事件的發(fā)生時(shí)刻和結(jié)束時(shí)刻（見下表，表中事件已按結(jié)束時(shí)刻升序排序）。一些在時(shí)間上沒有重疊的事件，可以構(gòu)成一個(gè)事件序列，如事件{2，8，10}。事件序列包含的事件數(shù)目，稱為該事件序列的長(zhǎng)度。請(qǐng)編程找出一個(gè)最長(zhǎng)的事件序列。事件編號(hào)01234567891011發(fā)生時(shí)刻130325641081515結(jié)束時(shí)刻34789101214151819209/17/202111算法分析：不妨用Begin[i]和End[i]表示事件i的開始時(shí)刻和結(jié)束時(shí)刻。則原題的要求就是找一個(gè)

3、最長(zhǎng)的序列a1

4、最小，并且線段的數(shù)目不超過N(1==M，那么顯然用M條長(zhǎng)度為1的線段可以覆蓋住所有的區(qū)間，所求的線段總長(zhǎng)為M。如果N=1，那么顯然所需線段總長(zhǎng)為：…如果N=2，相當(dāng)于N=1的情況下從某處斷開（從哪兒斷開呢？）。如果N=k呢？9/17/202116三、HDOJ_1050MovingTables題目鏈接SampleInput341020304050607080213220031010020803050SampleOu

5、tput1020309/17/202117算法分析：1、如果沒有交叉，總時(shí)間應(yīng)該是多少？2、影響搬運(yùn)時(shí)間的因素是什么？3、如果每趟處理都包含最大重疊，處理后的效果是什么？4、得出什么結(jié)論？9/17/202118HDOJ_1050源碼：#includeusingnamespacestd;intmain(){intt,i,j,N,P[200];ints,d,temp,k,min;cin>>t;for(i=0;i>N;for(j=0;j>s>>d;s=(s-1)/2;d=(d-

6、1)/2;if(s>d){temp=s;s=d;d=temp;}for(k=s;k<=d;k++)P[k]++;}min=-1;for(j=0;j<200;j++)if(P[j]>min)min=P[j];cout<

7、21ACM-ICPCAsiaRegional,2004,ShanghaiProblemHTianJi—TheHorseRacing9/17/202122示意圖：928371748795928371748795-200-200-200928371748795-200+200+2009/17/202123談?wù)勛约旱南敕ā?/17/202124Case1:King:200180160Tianji:1901701