貪心算法分析

2023/4/31第三講貪心算法

（GreedyAlgorithm）2023/4/32導(dǎo)引問(wèn)題：FatMouse‘Trade（1781）2023/4/33所謂“貪心算法”是指： 在對(duì)問(wèn)題求解時(shí)，總是作出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體上加以考慮，它所作出的僅僅是在某種意義上的局部最優(yōu)解（是否是全局最優(yōu)，需要證明）。2023/4/34特別說(shuō)明： 若要用貪心算法求解某問(wèn)題的整體最優(yōu)解，必須首先證明貪心思想在該問(wèn)題的應(yīng)用結(jié)果就是最優(yōu)解！！2023/4/35用事實(shí)說(shuō)話——2023/4/36一、事件序列問(wèn)題

已知N個(gè)事件的發(fā)生時(shí)刻和結(jié)束時(shí)刻（見(jiàn)下表，表中事件已按結(jié)束時(shí)刻升序排序）。一些在時(shí)間上沒(méi)有重疊的事件，可以構(gòu)成一個(gè)事件序列，如事件{2，8，10}。事件序列包含的事件數(shù)目，稱為該事件序列的長(zhǎng)度。請(qǐng)編程找出一個(gè)最長(zhǎng)的事件序列。事件編號(hào)01234567891011發(fā)生時(shí)刻130325641081515結(jié)束時(shí)刻34789101214151819202023/4/37算法分析：不妨用Begin[i]和End[i]表示事件i的開(kāi)始時(shí)刻和結(jié)束時(shí)刻。則原題的要求就是找一個(gè)最長(zhǎng)的序列a1<a2<…<an，滿足：Begin[a1]<End[a1]<=…<=Begin[an]<End[an]可以證明，如果在可能的事件a1<a2<…<an中選取在時(shí)間上不重疊的最長(zhǎng)序列，那么一定存在一個(gè)包含a1（結(jié)束最早）的最長(zhǎng)序列。（證明：略）2023/4/38思考題1782

今年暑假不AC2023/4/39二、區(qū)間覆蓋問(wèn)題

用i來(lái)表示x軸上坐標(biāo)為[i-1,i]的區(qū)間（長(zhǎng)度為1），并給出M(1=<M=<200)個(gè)不同的整數(shù)，表示M個(gè)這樣的區(qū)間。現(xiàn)在讓你畫(huà)幾條線段覆蓋住所有的區(qū)間，條件是：每條線段可以任意長(zhǎng)，但是要求所畫(huà)線段之和最小，并且線段的數(shù)目不超過(guò)N(1=<N=<50)。例如：M=5個(gè)整數(shù)1、3、4、8和11表示區(qū)間，要求所用線段不超過(guò)N=3條012345678910112023/4/310算法分析：如果N>=M，那么顯然用M條長(zhǎng)度為1的線段可以覆蓋住所有的區(qū)間，所求的線段總長(zhǎng)為M。如果N=1，那么顯然所需線段總長(zhǎng)為：…如果N=2，相當(dāng)于N=1的情況下從某處斷開(kāi)（從哪兒斷開(kāi)呢？）。如果N=k呢？2023/4/311三、JLNUOJ_1783MovingTablesSampleInput

3

4

1020

3040

5060

7080

2

13

2200

3

10100

2080

3050

SampleOutput

10

20

30

2023/4/312算法分析：1、如果沒(méi)有交叉，總時(shí)間應(yīng)該是多少？2、影響搬運(yùn)時(shí)間的因素是什么？3、如果每趟處理都包含最大重疊，處理后的效果是什么？4、得出什么結(jié)論？2023/4/313貪心算法的基本步驟

1、從問(wèn)題的某個(gè)初始解出發(fā)。2、采用循環(huán)語(yǔ)句，當(dāng)可以向求解目標(biāo)前進(jìn)一步時(shí)，就根據(jù)局部最優(yōu)策略，得到一個(gè)部分解，縮小問(wèn)題的范圍或規(guī)模。3、將所有部分解綜合起來(lái)，得到問(wèn)題的最終解。2023/4/314思考：田忌賽馬（1745）928371748795-200-200-200928371748795-200+200+2002023/4/315Case1:King:200180160Tianji:1901701502023/4/316Case2:King:200180160Tianji:1801701502023/4/317Case3:King:200180160Tianji:1801551502023/4/318總體的思路是什么？本題小結(jié)——算法：一：如果田忌的最快的馬比齊威王最快的馬快，則用它來(lái)比，先贏一場(chǎng)；二：如果田忌的最慢的馬比齊威王最慢的馬快，也用它來(lái)比，先贏一場(chǎng)；三：如果不同于前兩種情況的任何一種情況都是用田忌的最慢的馬來(lái)和齊威王最快的馬比；先輸一場(chǎng)，這叫懂得取舍~~2023/4/3192023/4/320提醒：

很多貪心類型的題目都象本題一樣，不是最樸素的貪心，而是需要做一些變化，對(duì)于我們，關(guān)鍵是找到貪心的本質(zhì)！2023/4/321Kruskal在1956年提出了1個(gè)最小生成樹(shù)算法，它的思路很容易理解。設(shè)G=(V,E)是一個(gè)連通帶權(quán)圖，V={1,2,…,n}。將圖中的邊按其權(quán)值由小到大排序，然后作如下的貪婪選擇，由小到大順序選取各條邊，若選某邊后不形成回路，則將其保留作為樹(shù)的一條邊；若選某邊后形成回路，則將其舍棄，以后也不再考慮。如此依次進(jìn)行，到選夠（n-1）條邊即得到最小生成樹(shù)。最小生成樹(shù)（1664）：例如，對(duì)于下圖中的帶權(quán)圖各邊按權(quán)值排序?yàn)椋篸13=1d46=2d25=3d36=4d14=

5d34=5d23=5d12=6d35=6d56=62023/4/322按Kruskal算法選取邊的過(guò)程如下圖所示2023/4/3232023/4/324貪心算法的常見(jiàn)前提操作：

排序！2023/4/325關(guān)于排序你在編程中常用的方法？自己寫(xiě)？（基本功）調(diào)用排序函數(shù)？（方便）常用排序函數(shù)qsort()C語(yǔ)言sort()C++2023/4/326關(guān)于qsort()頭文件:stdlib.h調(diào)用示例：intcmp(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;}intnum[10]={1,4,7,2,5,8,3,6,9,0};qsort(num,10,sizeof(num[0]),cmp);詳細(xì)使用方法見(jiàn)論壇帖子——七種qsort排序方法/acm/discuss/thread.php?tid