貪心算法分析

1、2022-3-231第三講第三講貪心算法貪心算法（Greedy Algorithm）2022-3-232導(dǎo)引問題：導(dǎo)引問題：FatMouse TradeFatMouse Trade（17811781）2022-3-233所謂所謂“貪心算法貪心算法”是指：是指：在對問題求解時，總是作出在當(dāng)前看來是最好當(dāng)前看來是最好的選擇。也就是說，不從整體上加以考慮，它所作出的僅僅是在某種意義上的局部最優(yōu)解（是否是全局最優(yōu)，需要證明）。2022-3-234特別說明：特別說明：若要用貪心算法求解某問題的整體最優(yōu)解，必須首先證明貪心思想在該問題的應(yīng)用結(jié)果就是最優(yōu)解！2022-3-235用事實說話用事實說話2022-

2、3-236一、事件序列問題一、事件序列問題 已知N個事件的發(fā)生時刻和結(jié)束時刻（見下表，表中事件已按結(jié)束時刻升序排序）。一些在時間上沒有重疊的事件，可以構(gòu)成一個事件序列，如事件2，8，10。事件序列包含的事件數(shù)目，稱為該事件序列的長度。請編程找出一個最長的事件序列。事件編號 0 1 2 3 45678910 11發(fā)生時刻 1 3 0 3 2564 10 815 15結(jié)束時刻 3 4 7 8 9 10 12 14 15 18 19 202022-3-237算法分析：算法分析：n不妨用Begini和Endi表示事件i的開始時刻和結(jié)束時刻。則原題的要求就是找一個最長的序列a1a2an，滿足：Begin

3、a1Enda1= BeginanEndan可以證明，如果在可能的事件a1a2an中選取在時間上不重疊的最長序列，那么一定存在一個包含a1（結(jié)束最早）的最長序列。（證明：略）2022-3-238思考題思考題n17821782 今年暑假不今年暑假不ACAC2022-3-239 二、區(qū)間覆蓋問題二、區(qū)間覆蓋問題 用i來表示x軸上坐標(biāo)為i-1,i的區(qū)間（長度為1），并給出M(1=M=200)個不同的整數(shù)，表示M個這樣的區(qū)間?，F(xiàn)在讓你畫幾條線段覆蓋住所有的區(qū)間，條件是：每條線段可以任意長，但是要求所畫線段之和最小，并且線段的數(shù)目不超過N(1=N=M，那么顯然用M條長度為1的線段可以覆蓋住所有的區(qū)間，所求

4、的線段總長為M。n如果N=1，那么顯然所需線段總長為：n如果N=2，相當(dāng)于N=1的情況下從某處斷開（從哪兒斷開呢？）。n如果N=k呢？2022-3-2311三、三、JLNUJLNUOJ_1OJ_1783783 Moving Tables 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 2022-3-2312算法分析：算法分析：1、如果沒有交叉，總時間應(yīng)該是多少？2、影響搬運時間的因素是什么？3、如果每趟處理都包含最大重疊，處理

5、后的效果是什么？4、得出什么結(jié)論？2022-3-2313貪心算法的基本步驟貪心算法的基本步驟 1、從問題的某個初始解出發(fā)。2、采用循環(huán)語句，當(dāng)可以向求解目標(biāo)前進(jìn)一步時，就根據(jù)局部最優(yōu)策略，得到一個部分解，縮小問題的范圍或規(guī)模。3、將所有部分解綜合起來，得到問題的最終解。2022-3-2314思考：思考：田忌賽馬（田忌賽馬（1745）928371748795-200-200-200928371748795-200+200+2002022-3-2315Case 1:Case 1:King: 200 180 160King: 200 180 160Tianji: 190 170 150Tianji:

6、 190 170 1502022-3-2316Case 2:Case 2:King: 200 180 160King: 200 180 160Tianji: 180 170 150Tianji: 180 170 1502022-3-2317Case 3:Case 3:King: 200 180 160King: 200 180 160Tianji: 180 155 150Tianji: 180 155 1502022-3-2318總體的思路是什么？總體的思路是什么？本題小結(jié)本題小結(jié)算法：n一：如果田忌的最快的馬比齊威王最快的馬快，則用它來比，先贏一場；n二：如果田忌的最慢的馬比齊威王最慢的馬快

7、，也用它來比，先贏一場；n三：如果不同于前兩種情況的任何一種情況都是用田忌的最慢的馬來和齊威王最快的馬比；先輸一場，這叫懂得取舍2022-3-23192022-3-2320提醒：提醒：很多貪心類型的題目都象本題一樣，不是最樸素的貪心，而是需要做一些變化，對于我們，關(guān)鍵是找到貪心的本質(zhì)！2022-3-2321Kruskal 在1956年提出了1個最小生成樹算法，它的思路很容易理解。設(shè)G=(V,E)是一個連通帶權(quán)圖，V=1,2,n。將圖中的邊按其權(quán)值由小到大排序，然后作如下的貪婪選擇，由小到大順序選取各條邊，若選某邊后不形成回路，則將其保留作為樹的一條邊；若選某邊后形成回路，則將其舍棄，以后也不再

8、考慮。如此依次進(jìn)行，到選夠（n-1）條邊即得到最小生成樹。最小生成樹（最小生成樹（1664）：）：例如，對于下圖中的帶權(quán)圖n各邊按權(quán)值排序為：nd13=1 d46=2 d25=3 d36=4 d14 = 5nd34=5 d23=5 d12=6 d35=6 d56=62022-3-2322按Kruskal算法選取邊的過程如下圖所示2022-3-23232022-3-2324貪心算法的常見前提操作：貪心算法的常見前提操作： 排序！2022-3-2325關(guān)于排序關(guān)于排序n你在編程中常用的方法？n自己寫？（基本功）n調(diào)用排序函數(shù)？（方便）n常用排序函數(shù)nqsort() C語言nsort() C+2022-3-2326關(guān)于關(guān)于qsort()n頭文件: stdlib.hn調(diào)用示例：int cmp ( const void *a , const void *b ) return *(int *)a- *(int *)b; int num10=1,4,7,2,5,8,3,6,9,0; qsort(num,10,sizeof(