貪心算法ppt課件

1、天津大學(xué)天津大學(xué)ACM講座講座貪心算法及其應(yīng)用貪心算法及其應(yīng)用05級(jí)QQ：591294402Email：1；.主要內(nèi)容主要內(nèi)容貪心算法簡(jiǎn)介貪心算法簡(jiǎn)介貪心算法應(yīng)用貪心算法應(yīng)用 最優(yōu)裝載問題單源最短路徑問題區(qū)間問題哈夫曼編碼練習(xí)題目練習(xí)題目2；.貪心算法簡(jiǎn)介 貪心算法是一個(gè)解決最優(yōu)子結(jié)構(gòu)問題的算法。顧名思義，貪心算法總是做出在當(dāng)前看貪心算法是一個(gè)解決最優(yōu)子結(jié)構(gòu)問題的算法。顧名思義，貪心算法總是做出在當(dāng)前看來最好的選擇，也就是說貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種來最好的選擇，也就是說貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。意義上的局部最優(yōu)選擇。3

2、；.貪心算法簡(jiǎn)介 雖然貪心算法不能對(duì)所有問題都得到整體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整雖然貪心算法不能對(duì)所有問題都得到整體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解。例如，圖的單源最短路徑問題，最小生成樹問題等。體最優(yōu)解。例如，圖的單源最短路徑問題，最小生成樹問題等。 在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。解的很好近似。4；.應(yīng)用應(yīng)用11最優(yōu)裝載最優(yōu)裝載問題：?jiǎn)栴}：有一批集裝箱要裝上一艘載重量為有一批集裝箱要裝上一艘載重量為 c 的輪船，其中集裝箱的輪船，其中集裝箱 i 的重量為的重量為 , ,在

3、裝載在裝載體積不受限制的情況下，應(yīng)如何裝載才能把盡可能多的集裝箱裝上輪船？體積不受限制的情況下，應(yīng)如何裝載才能把盡可能多的集裝箱裝上輪船？iw5；.應(yīng)用應(yīng)用11最優(yōu)裝載最優(yōu)裝載本題可形式化描述為本題可形式化描述為 max 其中，變量其中，變量 = 0表示不裝入集裝箱表示不裝入集裝箱i ， =1表示裝入集裝箱表示裝入集裝箱iinix1ciinixw1ni11 ,0，ixixix6；.應(yīng)用應(yīng)用11最優(yōu)裝載最優(yōu)裝載本例顯然可用貪心算法求解。本例顯然可用貪心算法求解。將集裝箱按重量由小到大排序，重量最輕者先裝，每一次都挑選剩余集裝箱中將集裝箱按重量由小到大排序，重量最輕者先裝，每一次都挑選剩余集裝箱中

4、最輕的裝入，直到不能裝入為止。得到本問題的一個(gè)最優(yōu)解。最輕的裝入，直到不能裝入為止。得到本問題的一個(gè)最優(yōu)解。實(shí)現(xiàn)代碼如下：實(shí)現(xiàn)代碼如下：7；.應(yīng)用應(yīng)用11最優(yōu)裝載最優(yōu)裝載#include #include using namespace std;const int N = 10002;struct nodeint id;int weight; aN;bool xN;int cmp( node a, node b )return a.weight b.weight;/定義的比較函數(shù)定義的比較函數(shù)cmp，/用于排序用于排序int main()int i,c,n,nc;while (scanf(%d

5、%d, &n, &c) != EOF) for (i = 0; i n; i+) scanf (%d, &a i .weight);a i .id = i; sort (a, a + n, cmp);8；.應(yīng)用應(yīng)用11最優(yōu)裝載最優(yōu)裝載memset (x, 0, sizeof( x );/先清零先清零for (i = nc = 0; i n ; i+)/nc為當(dāng)前裝入輪船的重量為當(dāng)前裝入輪船的重量if (nc + a i .weight = c)nc += a i .weight;x a i .id = 1; for (i = 0; i n; i+)/輸出結(jié)果輸出結(jié)果if

6、 (x i = 1)printf( %dn, i );return 0;9；.應(yīng)用應(yīng)用22單源最短路徑單源最短路徑問題描述 已知圖G=(V,E)，我們希望找出從某個(gè)給定源頂點(diǎn)sV到每個(gè)頂點(diǎn)vV的最短路徑。Dijkstra算法 每次在剩余的點(diǎn)中挑選距離源點(diǎn)s最近的點(diǎn)。直到找到目的頂點(diǎn)d。10；. 應(yīng)用應(yīng)用2-2-Dijkstra(G,w,s)initialize-single-sorce(G,s)S Q Vwhile(Q != ) do u min(Q) S Su for 每個(gè)與u相鄰的定點(diǎn)v relax(u,v,w) 因?yàn)镈ijkstra算法總是在V-S中選擇“最輕”或“最近”的定點(diǎn)插入集合S

7、中，所以我們說它使用了貪心貪心策略。11；.應(yīng)用應(yīng)用22單源最短路徑單源最短路徑Dijkstra是應(yīng)用貪心算法設(shè)計(jì)策略的一個(gè)典型例子。源點(diǎn)到定點(diǎn)是應(yīng)用貪心算法設(shè)計(jì)策略的一個(gè)典型例子。源點(diǎn)到定點(diǎn)u的最短路為的最短路為distu。它這種貪心選擇為什么能導(dǎo)致最優(yōu)解呢？它這種貪心選擇為什么能導(dǎo)致最優(yōu)解呢？簡(jiǎn)單證明（反證法）簡(jiǎn)單證明（反證法）假設(shè)存在一條從源點(diǎn)假設(shè)存在一條從源點(diǎn)s s到到u u且長(zhǎng)度比且長(zhǎng)度比distu更短的路，設(shè)這條路經(jīng)過在更短的路，設(shè)這條路經(jīng)過在S S之外的定點(diǎn)之外的定點(diǎn)x x最最后到達(dá)后到達(dá)u,u,則則distx = d(s,x)d d(s,x) + d(x,u) = d(s,u)

8、 = 0, ,故而得到故而得到 distx distu, ,而這樣的話而這樣的話x將會(huì)先于將會(huì)先于u被選入被選入S集合內(nèi)。這集合內(nèi)。這與假設(shè)條件矛盾。與假設(shè)條件矛盾。12；.應(yīng)用應(yīng)用22單源最短路徑單源最短路徑注：?jiǎn)卧醋疃搪窂降淖ⅲ簡(jiǎn)卧醋疃搪窂降膁ijkstra算法、最小生成樹的算法、最小生成樹的Prim算法和算法和Kruskal算法都可以看做算法都可以看做是應(yīng)用貪心算法設(shè)計(jì)策略的典型例子。是應(yīng)用貪心算法設(shè)計(jì)策略的典型例子。11月月2日的講座已經(jīng)講過這些了，這里不再贅述。日的講座已經(jīng)講過這些了，這里不再贅述。這里只舉一個(gè)簡(jiǎn)單例子：這里只舉一個(gè)簡(jiǎn)單例子：TOJ 2976題目描述：要尋找從商店到賽

9、場(chǎng)的最短的路線。題目描述：要尋找從商店到賽場(chǎng)的最短的路線。輸入：每組數(shù)據(jù)兩個(gè)整數(shù)輸入：每組數(shù)據(jù)兩個(gè)整數(shù)N N、M M（N=100N=100，M=10000M=10000），），N N表示大街上有幾個(gè)路口，表示大街上有幾個(gè)路口，1 1是商店，是商店，N N是賽場(chǎng)，是賽場(chǎng)，M M表示有幾條路。表示有幾條路。N=M=0N=M=0表示輸入結(jié)束。接下來表示輸入結(jié)束。接下來M M行，每行行，每行3 3個(gè)整數(shù)個(gè)整數(shù)A A，B B，C C（1=A,B=N,1=C=10001=A,B=N,1=C=1000）, ,表示在路口表示在路口A A與與B B之間有一條路，工作人員需之間有一條路，工作人員需C C分鐘走過這

10、分鐘走過這條路。條路。輸出：輸出：對(duì)每組輸入，輸出一行，表示工作人員從商店走到賽場(chǎng)的最短時(shí)間對(duì)每組輸入，輸出一行，表示工作人員從商店走到賽場(chǎng)的最短時(shí)間13；.應(yīng)用應(yīng)用22單源最短路徑單源最短路徑樣例輸入：樣例輸入：2 11 2 33 31 2 52 3 53 1 20 0樣例輸出：樣例輸出：3214；.應(yīng)用應(yīng)用22單源最短路徑單源最短路徑直接運(yùn)用Dijkstra算法即可。15；.應(yīng)用應(yīng)用3區(qū)間問題區(qū)間問題在比賽中，有很多問題最終都能轉(zhuǎn)化為區(qū)間問題：例如從若干個(gè)區(qū)間中選出一些滿足在比賽中，有很多問題最終都能轉(zhuǎn)化為區(qū)間問題：例如從若干個(gè)區(qū)間中選出一些滿足一定條件的區(qū)間、將各個(gè)區(qū)間分配到一些資源中、

11、或者將一些區(qū)間以某種順序放置等。一定條件的區(qū)間、將各個(gè)區(qū)間分配到一些資源中、或者將一些區(qū)間以某種順序放置等。如活動(dòng)安排問題、機(jī)器調(diào)度問題等等。如活動(dòng)安排問題、機(jī)器調(diào)度問題等等。這類問題變化繁多，解法各異。下面介紹幾種常見模型。這類問題變化繁多，解法各異。下面介紹幾種常見模型。16；.區(qū)間問題區(qū)間問題1.最大區(qū)間調(diào)度問題最大區(qū)間調(diào)度問題數(shù)軸上有n個(gè)區(qū)間，選出最多的區(qū)間，使得這些區(qū)間不互相重疊。算法：按右端點(diǎn)坐標(biāo)排序依次選擇所有能選的區(qū)間17；.區(qū)間問題區(qū)間問題1.最大區(qū)間調(diào)度問題最大區(qū)間調(diào)度問題證明證明例題：例題：TOJ 2867某人想要參加一系列活動(dòng)，已知某人想要參加一系列活動(dòng)，已知每個(gè)活動(dòng)的

12、開始時(shí)間和持續(xù)時(shí)間，問他每個(gè)活動(dòng)的開始時(shí)間和持續(xù)時(shí)間，問他最多能參加幾個(gè)活動(dòng)。最多能參加幾個(gè)活動(dòng)。Sample Input50 35 109 23 42 20Sample Output318；.區(qū)間問題區(qū)間問題1.最大區(qū)間調(diào)度問題最大區(qū)間調(diào)度問題分析：本題已知每個(gè)活動(dòng)的起始時(shí)間和持續(xù)時(shí)間，由此可得到活動(dòng)的起始時(shí)間和終止分析：本題已知每個(gè)活動(dòng)的起始時(shí)間和持續(xù)時(shí)間，由此可得到活動(dòng)的起始時(shí)間和終止時(shí)間，即各區(qū)間的兩個(gè)端點(diǎn)。顯然，這是最大區(qū)間調(diào)度問題。時(shí)間，即各區(qū)間的兩個(gè)端點(diǎn)。顯然，這是最大區(qū)間調(diào)度問題。 應(yīng)用上面所講的貪心算法即可求解。應(yīng)用上面所講的貪心算法即可求解。19；.區(qū)間問題區(qū)間問題2.多個(gè)

13、資源的調(diào)度問題多個(gè)資源的調(diào)度問題有有n個(gè)區(qū)間和無限多的資源，每個(gè)資源上的區(qū)間之間不互相重疊。將每個(gè)區(qū)間都分配到個(gè)區(qū)間和無限多的資源，每個(gè)資源上的區(qū)間之間不互相重疊。將每個(gè)區(qū)間都分配到某個(gè)資源中，使用到的資源數(shù)量最小。某個(gè)資源中，使用到的資源數(shù)量最小。 20；.定義區(qū)間集合深度d為包含任意一點(diǎn)的區(qū)間數(shù)量的最大值至少需要d個(gè)資源算法：計(jì)算出d按左端點(diǎn)坐標(biāo)排序依次將區(qū)間任意地分配到d個(gè)資源中21；.區(qū)間問題區(qū)間問題2.多個(gè)資源的調(diào)度問題多個(gè)資源的調(diào)度問題關(guān)鍵：關(guān)鍵：區(qū)間深度區(qū)間深度d d如何計(jì)算？如何計(jì)算？d d的計(jì)算方法：的計(jì)算方法：將每個(gè)區(qū)間拆成兩個(gè)事件點(diǎn)，按坐標(biāo)從小到大排序，順序處理每個(gè)區(qū)間。

14、記錄將每個(gè)區(qū)間拆成兩個(gè)事件點(diǎn)，按坐標(biāo)從小到大排序，順序處理每個(gè)區(qū)間。記錄一個(gè)值，表示當(dāng)前點(diǎn)被包含次數(shù)。每次遇到區(qū)間的左端點(diǎn)就一個(gè)值，表示當(dāng)前點(diǎn)被包含次數(shù)。每次遇到區(qū)間的左端點(diǎn)就+1+1，遇到右端點(diǎn)就，遇到右端點(diǎn)就-1-1。的。的值就是在該過程中的最大值。注意兩個(gè)相同坐標(biāo)不同類型的事件點(diǎn)的位置關(guān)系和區(qū)間值就是在該過程中的最大值。注意兩個(gè)相同坐標(biāo)不同類型的事件點(diǎn)的位置關(guān)系和區(qū)間是否能在端點(diǎn)處重疊有關(guān)，這在排序過程中應(yīng)該注意。是否能在端點(diǎn)處重疊有關(guān)，這在排序過程中應(yīng)該注意。22；.區(qū)間問題區(qū)間問題2.多個(gè)資源的調(diào)度問題多個(gè)資源的調(diào)度問題例：例：TOJ 2894 Meetings（07年保研復(fù)試題）年

15、保研復(fù)試題）題目描述：題目描述：給出會(huì)議的起止時(shí)間（即給出了各個(gè)區(qū)間），問安排這些會(huì)議最少需要多少個(gè)會(huì)議室給出會(huì)議的起止時(shí)間（即給出了各個(gè)區(qū)間），問安排這些會(huì)議最少需要多少個(gè)會(huì)議室?（一個(gè)會(huì)議結(jié)束的時(shí)刻，另一個(gè)會(huì)議可以馬上開始）（一個(gè)會(huì)議結(jié)束的時(shí)刻，另一個(gè)會(huì)議可以馬上開始）分析：會(huì)議室分析：會(huì)議室多個(gè)資源；會(huì)議多個(gè)資源；會(huì)議區(qū)間；將每個(gè)區(qū)間都分配給某個(gè)資源，使用到的資區(qū)間；將每個(gè)區(qū)間都分配給某個(gè)資源，使用到的資源數(shù)量最小，即要求解的是區(qū)間深度源數(shù)量最小，即要求解的是區(qū)間深度d。23；.注意：前面提到，加注意：前面提到，加1與減與減1的先后順序與每個(gè)區(qū)間在端點(diǎn)處可否重疊有關(guān)。對(duì)本題而的先后順序與

16、每個(gè)區(qū)間在端點(diǎn)處可否重疊有關(guān)。對(duì)本題而言，顯然要求可以重疊，故應(yīng)該先減言，顯然要求可以重疊，故應(yīng)該先減1再加再加1。算法主體部分可參加下頁代碼。算法主體部分可參加下頁代碼。其中，其中，a a 和和b b 分別存放各區(qū)間的左端點(diǎn)和右端點(diǎn)。分別存放各區(qū)間的左端點(diǎn)和右端點(diǎn)。j1j1和和j2j2分別是數(shù)組分別是數(shù)組a a 、b b 的下標(biāo)。的下標(biāo)。r r是貫穿整個(gè)是貫穿整個(gè)forfor循環(huán)的變量，遇到區(qū)間右端點(diǎn)則加循環(huán)的變量，遇到區(qū)間右端點(diǎn)則加1 1，遇到區(qū)間左端點(diǎn)則減，遇到區(qū)間左端點(diǎn)則減1 1。result result 為為forfor循環(huán)過程中循環(huán)過程中r r的最大值，即區(qū)間深度的最大值，即區(qū)間

17、深度d d。TOJ 289424；.TOJ 2894MAX = MIN = 0; for (i = 0; i n; i+) scanfscanf (%d %d, &a i , &b i ); (%d %d, &a i , &b i ); if if ( MAX b i ) ( MAX a i ) (MIN a i ) MIN = a i ; MIN = a i ; sortsort (a, a + n); /(a, a + n); /對(duì)左端點(diǎn)進(jìn)行排序?qū)ψ蠖它c(diǎn)進(jìn)行排序sortsort (b, b + n); /(b, b + n); /對(duì)右端點(diǎn)進(jìn)行排序?qū)τ叶它c(diǎn)進(jìn)行

18、排序j1 = j2 = 0;j1 = j2 = 0;result = 0;result = 0;r = 0;r = 0; 25；.TOJ 2894 for (i = MIN; i = MAX;) /MIN和和MAX分別是所有區(qū)間最左端點(diǎn)和最右端點(diǎn)分別是所有區(qū)間最左端點(diǎn)和最右端點(diǎn)if (i= b j2 ) r -; j2 +; /每次遇到區(qū)間右端點(diǎn)則減每次遇到區(qū)間右端點(diǎn)則減1if (i = a j1 ) r +; j1 +; /每次遇到區(qū)間左端點(diǎn)則加每次遇到區(qū)間左端點(diǎn)則加1if (k r) result = r;/ result 為最后結(jié)果為最后結(jié)果if (j1 n & j2 n) i

19、= ( b j2 a j1 ? b j2 : a j1 ); else if (j1 = n) i = a j1 ; else if (j2 = n) i = b j2 ; else break; printf( “%dn”, result ); /最后輸出結(jié)果最后輸出結(jié)果26；.區(qū)間問題區(qū)間問題3.有最終期限的區(qū)間調(diào)度問題有最終期限的區(qū)間調(diào)度問題有n個(gè)長(zhǎng)度固定、但位置可變的區(qū)間，將它們?nèi)糠胖迷?,+)上。每個(gè)區(qū)間有兩個(gè)已知參數(shù)：長(zhǎng)度ti和最終期限di，設(shè)fi為其右端點(diǎn)坐標(biāo)。定義放置所有區(qū)間，使它們不互相重疊且最大延遲L最小。 iiiiiiidfifdfifdfl0 inilL1max27；

20、.算法：按最終期限排序順序安排各區(qū)間最終期限最終期限di28；.例題：Europe - Southeastern 2007 Problem D一個(gè)銀行家收到了一個(gè)銀行家收到了N個(gè)貸款申請(qǐng)，每個(gè)貸款最晚都要在個(gè)貸款申請(qǐng)，每個(gè)貸款最晚都要在 前完成，利潤(rùn)前完成，利潤(rùn)為為 ，每個(gè)貸款均需要一個(gè)單位時(shí)間來處理，銀行在同一時(shí)間內(nèi)最多可接受，每個(gè)貸款均需要一個(gè)單位時(shí)間來處理，銀行在同一時(shí)間內(nèi)最多可接受L個(gè)貸款，個(gè)貸款， 問如何安排能使獲得利潤(rùn)最大？問如何安排能使獲得利潤(rùn)最大？分析：將每個(gè)貸款申請(qǐng)看作一個(gè)單位長(zhǎng)度、位置可變且?guī)?quán)的區(qū)間，則題目轉(zhuǎn)化為選出一些區(qū)間，將它們不互相重疊地放在L個(gè)資源上，使利潤(rùn)最大，

21、且區(qū)間的左端點(diǎn)不得超過 ?？捎秘澬乃惴ń鉀Q該問題。100000iidd區(qū)間問題區(qū)間問題3.有最終期限的區(qū)間調(diào)度問題有最終期限的區(qū)間調(diào)度問題ipid29；.區(qū)間問題區(qū)間問題3.有最終期限的區(qū)間調(diào)度問題有最終期限的區(qū)間調(diào)度問題算法：算法：將這些區(qū)間按照權(quán)值從大到小排序，順序處理每個(gè)區(qū)間。設(shè) 由于區(qū)間都是單位長(zhǎng)度的，我們可以用一維數(shù)組 來記錄當(dāng)前的情況,表示 被覆蓋次數(shù)，根據(jù)題意有 處理第i個(gè)區(qū)間時(shí)，若可以選擇該區(qū)間， （即 ），則將該區(qū)間放置到一個(gè)i最大的一個(gè)位置，即 ，否則就不選擇該區(qū)間。1, i iDiis1 iNidD1maxLis 0 Lisiidi|max0 Lisdii,030；.區(qū)間

22、問題區(qū)間問題3.有最終期限的區(qū)間調(diào)度問題有最終期限的區(qū)間調(diào)度問題與上例相似的一道題：與上例相似的一道題：TOJ 1681唯一的一點(diǎn)不同是唯一的一點(diǎn)不同是toj 1681同一時(shí)刻只能處理一件產(chǎn)品，即上頁算法中的同一時(shí)刻只能處理一件產(chǎn)品，即上頁算法中的L是是1。因此。因此toj 1681要簡(jiǎn)單一些。大家回去可以按照上述算法做一做。要簡(jiǎn)單一些。大家回去可以按照上述算法做一做。參見如下部分代碼：參見如下部分代碼：sort (a, a + n, cmp);memset (s, -1, sizeof(s);for (i = 0; i = 0; j-)if (s j = -1)s j = i;break;3

23、1；.區(qū)間問題區(qū)間問題4.最小區(qū)間覆蓋問題最小區(qū)間覆蓋問題有n個(gè)區(qū)間，選擇盡量少的區(qū)間，使得這些區(qū)間完全覆蓋某線段s,t。算法：按左端點(diǎn)坐標(biāo)排序每次選擇覆蓋點(diǎn)s的區(qū)間中右端點(diǎn)坐標(biāo)最大的一個(gè)，并更新s直到所選區(qū)間已包含t32；.區(qū)間問題區(qū)間問題5 5. .區(qū)間和點(diǎn)的有關(guān)問題區(qū)間和點(diǎn)的有關(guān)問題有n個(gè)區(qū)間，m個(gè)點(diǎn)。若某區(qū)間包含了某點(diǎn)，則構(gòu)成一對(duì)匹配關(guān)系。選出最多的區(qū)間和相同數(shù)量的點(diǎn)，使對(duì)應(yīng)的區(qū)間和點(diǎn)構(gòu)成匹配關(guān)系。 33；.算法： 所有點(diǎn)按坐標(biāo)排序選取包含該點(diǎn)且右端點(diǎn)坐標(biāo)最小的區(qū)間時(shí)間復(fù)雜度時(shí)間復(fù)雜度O(nm)O(nm)34；.優(yōu)化按區(qū)間左端點(diǎn)排序，得到有序表維護(hù)二叉堆，以區(qū)間右端點(diǎn)為關(guān)鍵字所有點(diǎn)按坐

24、標(biāo)從小到大依次處理時(shí)間復(fù)雜度時(shí)間復(fù)雜度O(nlogn+mlogm)O(nlogn+mlogm)35；.區(qū)間問題總結(jié)區(qū)間問題總結(jié)有序性有序性大多數(shù)問題都要先排序，經(jīng)常要用到結(jié)構(gòu)體、寫比較函數(shù)。排序的時(shí)候大多數(shù)問題都要先排序，經(jīng)常要用到結(jié)構(gòu)體、寫比較函數(shù)。排序的時(shí)候要選好排序的關(guān)鍵字。要選好排序的關(guān)鍵字。算法的選擇與設(shè)計(jì)算法的選擇與設(shè)計(jì)優(yōu)化優(yōu)化數(shù)據(jù)結(jié)構(gòu)的選擇：有時(shí)候?yàn)榱吮苊獬瑫r(shí)，要進(jìn)行適當(dāng)優(yōu)化，比如用二叉堆數(shù)據(jù)結(jié)構(gòu)的選擇：有時(shí)候?yàn)榱吮苊獬瑫r(shí)，要進(jìn)行適當(dāng)優(yōu)化，比如用二叉堆來維護(hù)，等等。來維護(hù)，等等。 36；.應(yīng)用應(yīng)用4哈夫曼編碼哈夫曼編碼哈夫曼編碼是用于數(shù)據(jù)文件壓縮的一個(gè)十分有效的編碼方法。其壓縮率

25、在哈夫曼編碼是用于數(shù)據(jù)文件壓縮的一個(gè)十分有效的編碼方法。其壓縮率在20%90%之之間。哈夫曼編碼是可變字長(zhǎng)編碼間。哈夫曼編碼是可變字長(zhǎng)編碼(VLC)的一種。的一種。 Huffman于于1952年提出一種編碼方法，年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長(zhǎng)度最短的碼字，有時(shí)稱之為最佳該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長(zhǎng)度最短的碼字，有時(shí)稱之為最佳編碼，一般就叫作編碼，一般就叫作Huffman編碼。編碼。 哈夫曼樹（即最優(yōu)二叉樹），帶權(quán)路徑長(zhǎng)度最小的哈夫曼樹（即最優(yōu)二叉樹），帶權(quán)路徑長(zhǎng)度最小的二叉樹。二叉樹。37；.應(yīng)用應(yīng)用4哈夫曼編碼哈夫曼編碼以自底向上的方式構(gòu)

26、造最優(yōu)二叉樹以自底向上的方式構(gòu)造最優(yōu)二叉樹T T。以。以|C|C|個(gè)葉子結(jié)點(diǎn)開始，執(zhí)行個(gè)葉子結(jié)點(diǎn)開始，執(zhí)行|C|-1|C|-1次的次的“合并合并”運(yùn)算后產(chǎn)生最終所要求的樹運(yùn)算后產(chǎn)生最終所要求的樹T T，每次找到兩個(gè)頻度最低的對(duì)象進(jìn)行合并，合并的結(jié)果是，每次找到兩個(gè)頻度最低的對(duì)象進(jìn)行合并，合并的結(jié)果是一個(gè)新對(duì)象，其頻度為被合并的兩個(gè)對(duì)象的頻度之和。最終使得一個(gè)新對(duì)象，其頻度為被合并的兩個(gè)對(duì)象的頻度之和。最終使得 （即樹（即樹T T的代價(jià)）最小。其中，的代價(jià)）最小。其中， f(c)cc出現(xiàn)的頻度；出現(xiàn)的頻度； c c的深度。的深度。 CcTcdcf)()()(cdT38；.應(yīng)用應(yīng)用4哈夫曼編碼哈夫

27、曼編碼例：例：共有6個(gè)字母，各自頻度如下：f:5 e:9 c:12b:13d:16a:4539；.應(yīng)用應(yīng)用4哈夫曼編碼哈夫曼編碼40；.應(yīng)用應(yīng)用4哈夫曼編碼哈夫曼編碼例題：例題：TOJ 2849題目大意：把一根長(zhǎng)木板切成要求的題目大意：把一根長(zhǎng)木板切成要求的n段，每段長(zhǎng)度段，每段長(zhǎng)度Li已知，共需切割已知，共需切割n-1次。每次切次。每次切割的花銷與切割之前木板長(zhǎng)度相等。求最小的花銷。割的花銷與切割之前木板長(zhǎng)度相等。求最小的花銷。n=20000;Li=50000.Sample Input Sample Output3 3485841；.應(yīng)用應(yīng)用4哈夫曼編碼哈夫曼編碼TOJ 2849嘗試不同的貪

28、心策略：對(duì)于Sample，三段8，5，8，答案34。 34 = 21 + 13 = （8 + 8 + 5）+（8 + 5）猜想貪心策略1：按照長(zhǎng)度排序，每次切割下剩余部分中最長(zhǎng)的？這種方法是否可行？不可行！不可行！ 原因：原因：反例：輸入：反例：輸入：5、6、8、9，按上面的猜想策略做，按上面的猜想策略做，9、8、6、5，每次切割前總長(zhǎng)，每次切割前總長(zhǎng)度分別是度分別是28、19、11，總花銷，總花銷=28+19+11=58.而實(shí)際上，這個(gè)例子的最優(yōu)解應(yīng)該是而實(shí)際上，這個(gè)例子的最優(yōu)解應(yīng)該是 56 = 28 + 11 + 17，也就是說第一次切成，也就是說第一次切成11和和17兩段，第二次把兩段，第二次把11切成切成5和和6兩段，第三兩段，第三次把次把17切成切成8和和9兩段。兩段。42；.應(yīng)用應(yīng)用4哈夫曼編碼哈夫曼編碼TOJ 2849注意數(shù)據(jù)范圍?？赡艹⒁鈹?shù)據(jù)范圍。可能超int，故而用，故而用long long。 參見如下代碼：參見如下代碼：