第4章-貪心法

1、1貪心算法又叫登山法，它的根本思想是逐步到達(dá)山頂，即逐步獲得最優(yōu)解，以逐步的局部最優(yōu)，達(dá)到最終的全局最優(yōu)。第第4章章 貪心法貪心法（Greedy Approach）24.1 貪心法的設(shè)計(jì)思想貪心法的設(shè)計(jì)思想4.2 貪心法的正確性證明貪心法的正確性證明4.3 對(duì)貪心法得不到最優(yōu)解情況的處理對(duì)貪心法得不到最優(yōu)解情況的處理4.4 貪心法的典型應(yīng)用貪心法的典型應(yīng)用 4.4.1 最優(yōu)前綴碼最優(yōu)前綴碼 4.4.2 最小生成樹最小生成樹 4.4.3 單源最短路徑單源最短路徑第第4章章 貪心法貪心法（Greedy Approach）3例：幣種統(tǒng)計(jì)問題例：幣種統(tǒng)計(jì)問題某單位給每個(gè)職工發(fā)工資（精確到元）。為了保證

2、不要臨某單位給每個(gè)職工發(fā)工資（精確到元）。為了保證不要臨時(shí)兌換零錢時(shí)兌換零錢, 且取款的張數(shù)最少，取工資前要統(tǒng)計(jì)出所有且取款的張數(shù)最少，取工資前要統(tǒng)計(jì)出所有職工的工資所需各種幣值職工的工資所需各種幣值(100,50,20,10,5,2,1元共七種元共七種)的的張數(shù)。張數(shù)。注：假若注：假若,某國(guó)的幣種是這樣的某國(guó)的幣種是這樣的,共共9種種: 100,70,50,20,10,7,5,2,1。4活動(dòng)選擇問題活動(dòng)選擇問題輸入：輸入：S =1, 2, , n為為n 項(xiàng)活動(dòng)的集合，項(xiàng)活動(dòng)的集合，si, fi 分別為活動(dòng)分別為活動(dòng) i 的開始和結(jié)束時(shí)間，的開始和結(jié)束時(shí)間，活動(dòng)活動(dòng) i 與與 j 相容相容 s

3、i fj 或或 sj fi .求：最大的兩兩相容的活動(dòng)集求：最大的兩兩相容的活動(dòng)集 A 實(shí)例實(shí)例策略策略1：排序使得：排序使得 s1 s2 sn，從前向后挑選，從前向后挑選策略策略2：排序使得：排序使得 f1s1 f2s2 fnsn，從前向后挑選，從前向后挑選策略策略3：排序使得：排序使得 f1 f2 fn，從前向后挑選，從前向后挑選以上策略中的挑選都要注意滿足相容性條件以上策略中的挑選都要注意滿足相容性條件4.1貪心法的設(shè)計(jì)思想貪心法的設(shè)計(jì)思想i12345678910si1325456882fi45679910111213兩個(gè)反例兩個(gè)反例 2310 2 5 8 10 15 20 2310 2

4、 5 8 10 15 20 策略策略1：S=1,2,3，s1=0, f1=20, s2=2, f2=5, s3=8, f3=15 策略策略2：S=1,2,3，s1=0, f1=8, s2=7, f2=9, s3=8, f3=15 6貪心算法貪心算法算法算法4.1 Greedy Select輸入：活動(dòng)集輸入：活動(dòng)集S，si，fi, i=1,2,n，且，且 f1 fn 輸出：輸出：A S，選中的活動(dòng)子集，選中的活動(dòng)子集 1. nlengthS / 活動(dòng)個(gè)數(shù)活動(dòng)個(gè)數(shù) 2. A1 3. j1 /已選入的最后一個(gè)活動(dòng)的標(biāo)號(hào)已選入的最后一個(gè)活動(dòng)的標(biāo)號(hào) 4. for i2 to n do 5. if si

5、fj /判斷相容性判斷相容性 6. then A A i 7. j i 8. return A 最后完成時(shí)間最后完成時(shí)間 t = max fk: k A 7輸入：輸入：S=1, 2, , 10i12345678910si1305356882fi45678910111213問題：如何證明該算法對(duì)所有的實(shí)例都能得到正確的解？問題：如何證明該算法對(duì)所有的實(shí)例都能得到正確的解？算法運(yùn)行實(shí)例算法運(yùn)行實(shí)例解解: : A = 1, 4, 8, t =11時(shí)間復(fù)雜度：排序時(shí)間復(fù)雜度：排序+活動(dòng)選擇活動(dòng)選擇=O(nlogn)+O(n)=O(nlogn)8算法的正確性證明算法的正確性證明證：證：S=1, 2, ,

6、 n是活動(dòng)集，是活動(dòng)集，且且 f1 fn 歸納基礎(chǔ)：歸納基礎(chǔ)：k=1, 證明存在最優(yōu)解包含活動(dòng)證明存在最優(yōu)解包含活動(dòng)1任取最優(yōu)解任取最優(yōu)解A, A中的活動(dòng)按截止時(shí)間遞增排列中的活動(dòng)按截止時(shí)間遞增排列. 如果如果A的第的第一個(gè)活動(dòng)為一個(gè)活動(dòng)為 j，j 1, 令令 A= (A j ) 1, 由于由于 f1 fj , A也是最優(yōu)解，且含有也是最優(yōu)解，且含有1. 定理定理4.1 算法算法Select 執(zhí)行到第執(zhí)行到第 k 步步, 選擇選擇 k 項(xiàng)活動(dòng)項(xiàng)活動(dòng) i1= 1, i2, , ik, 那么存在最優(yōu)解那么存在最優(yōu)解 A 包含包含 i1=1, i2, , ik .根據(jù)定理：針對(duì)上述問題，算法至多到第

7、根據(jù)定理：針對(duì)上述問題，算法至多到第 n 步得到最優(yōu)解步得到最優(yōu)解9)(,.,.,112121 kkkkiBiiiiBiii也是原問題的最優(yōu)解也是原問題的最優(yōu)解. .歸納步驟：假設(shè)命題對(duì)歸納步驟：假設(shè)命題對(duì) k 為真為真, 證明對(duì)證明對(duì) k+1 也為真也為真. 算法執(zhí)行到第算法執(zhí)行到第 k 步步, 選擇了活動(dòng)選擇了活動(dòng) i1=1, i2, , ik, 根據(jù)歸納假設(shè)根據(jù)歸納假設(shè)存在最優(yōu)解存在最優(yōu)解 A 包含包含 i1= 1, i2, , ik , A中剩下的活動(dòng)選自集合中剩下的活動(dòng)選自集合 S= i | i S, si fk, 且且 A = i1, i2, , ik B其中其中B是是S的最優(yōu)解的

8、最優(yōu)解.（若不然（若不然, S的最優(yōu)解為的最優(yōu)解為B*, B*的活動(dòng)的活動(dòng)比比 B多，那么多，那么B* 1, i2, , ik是是 S 的最優(yōu)解，且比的最優(yōu)解，且比 A的活的活動(dòng)多動(dòng)多,與與 A 的最優(yōu)性矛盾的最優(yōu)性矛盾.）根據(jù)歸納基礎(chǔ)，存在根據(jù)歸納基礎(chǔ)，存在 S的最優(yōu)解的最優(yōu)解B含有含有S中的第一個(gè)活動(dòng)，中的第一個(gè)活動(dòng)，即即ik+1, 且且|B|=|B|, 于是于是 算法正確性證明（續(xù)）算法正確性證明（續(xù)）10貪心算法的特點(diǎn)貪心算法的特點(diǎn)設(shè)計(jì)要素：設(shè)計(jì)要素：(1)貪心法適用于組合優(yōu)化問題貪心法適用于組合優(yōu)化問題. (2)求解過程是多步判斷過程，最終的判斷序列對(duì)應(yīng)于問題求解過程是多步判斷過程，

9、最終的判斷序列對(duì)應(yīng)于問題 的最優(yōu)解的最優(yōu)解. (3)判斷依據(jù)某種判斷依據(jù)某種“短視的短視的”貪心選擇性質(zhì)，性質(zhì)的好壞決貪心選擇性質(zhì)，性質(zhì)的好壞決 定了算法的成敗定了算法的成敗. (4)貪心法必須進(jìn)行正確性證明貪心法必須進(jìn)行正確性證明貪心法的優(yōu)勢(shì)：貪心法的優(yōu)勢(shì)：算法簡(jiǎn)單，時(shí)間和空間復(fù)雜性低算法簡(jiǎn)單，時(shí)間和空間復(fù)雜性低11 4.2 貪心法的正確性證明貪心法的正確性證明數(shù)學(xué)歸納法數(shù)學(xué)歸納法 1. 敘述一個(gè)描述算法正確性的命題敘述一個(gè)描述算法正確性的命題P(n)，n為算法步數(shù)或者為算法步數(shù)或者 問題規(guī)模問題規(guī)模 2. 歸納基礎(chǔ)：歸納基礎(chǔ)：P(1) 或或 P(n0)為真為真, n0為某個(gè)自然數(shù)為某個(gè)自然

10、數(shù) 3. 歸納步驟：歸納步驟：P(k) P(k+1) 第一數(shù)學(xué)歸納法第一數(shù)學(xué)歸納法 k(k | I |； 那么那么 I* 1是關(guān)于是關(guān)于 N 和和C的解且的解且 | I* 1| | I 1 | = | I| 與與 I 的最優(yōu)性矛盾的最優(yōu)性矛盾.正確性證明正確性證明14最小延遲調(diào)度最小延遲調(diào)度例例4.3 最小延遲調(diào)度最小延遲調(diào)度給定客戶集合給定客戶集合A， i A，ti 為服務(wù)時(shí)間，為服務(wù)時(shí)間，di 為客戶期待完成為客戶期待完成時(shí)間，時(shí)間，ti, di為正整數(shù)為正整數(shù). 一個(gè)一個(gè)調(diào)度調(diào)度是函數(shù)是函數(shù) f : AN，f(i)為客為客戶戶 i 的開始時(shí)間的開始時(shí)間. 求求最大延遲達(dá)到最小的調(diào)度，即求

11、最大延遲達(dá)到最小的調(diào)度，即求 f 使使得得)(maxminiiAifdtif )()(or)()(,iftjfjftifjiAjiji h(A,B) = |ba|minmaxBbAa15實(shí)例實(shí)例調(diào)度調(diào)度1： f1(1)=0, f1(2)=5, f1(3)=13, f1(4)=17, f1(5)=27 各任務(wù)延遲：各任務(wù)延遲：0, 1, 2, 16, 10; 最大延遲：最大延遲：16 1 2 3 4 5 5 13 17 27 30 調(diào)度調(diào)度2： f2(1)=0, f2(2)=15, f2(3)=23, f2(4)=5, f2(5)=27 各任務(wù)延遲：各任務(wù)延遲：0, 11, 12, 4, 10;

12、 最大延遲：最大延遲：12A=1, 2, 3, 4, 5, T=, D= 1 4 2 3 5 5 15 23 27 3016貪心策略選擇貪心策略選擇貪心策略貪心策略1：按照：按照 ti 從小到大安排任務(wù)從小到大安排任務(wù)貪心策略貪心策略2：按照：按照 di ti 從小到大安排任務(wù)從小到大安排任務(wù)貪心策略貪心策略3：按照：按照 di 從小到大安排任務(wù)從小到大安排任務(wù)策略策略1 對(duì)某些實(shí)例得不到最優(yōu)解對(duì)某些實(shí)例得不到最優(yōu)解. 反例：反例：t1=1, d1=100, t2=10, d2=10 策略策略2 對(duì)某些實(shí)例得不到最優(yōu)解對(duì)某些實(shí)例得不到最優(yōu)解. 反例：反例：t1=1, d1=2, t2=10,

13、d2=10 17算法設(shè)計(jì)算法設(shè)計(jì)算法算法4.3 Schedule 輸入：輸入：A, T, D輸出：輸出：f 1. 排序排序A使得使得 d1 d2 dn 2. f(1)0 3. i2 3. while i n do 4. f(i)f(i 1)+ti 1 /任務(wù)任務(wù)i-1結(jié)束時(shí)刻是任務(wù)結(jié)束時(shí)刻是任務(wù)i開始時(shí)刻開始時(shí)刻 5. ii+1設(shè)計(jì)思想：按完成時(shí)間從早到晚安排任務(wù)，沒有空閑設(shè)計(jì)思想：按完成時(shí)間從早到晚安排任務(wù)，沒有空閑 18交換論證：正確性證明交換論證：正確性證明算法的解的性質(zhì)：算法的解的性質(zhì)： (1) 沒有空閑時(shí)間沒有空閑時(shí)間, 沒有逆序沒有逆序. (2) 逆序逆序 (i, j): f(i)

14、 dj 引理引理4.14.1 所有沒有逆序、沒有空閑時(shí)間的調(diào)度具有相同的所有沒有逆序、沒有空閑時(shí)間的調(diào)度具有相同的最大延遲最大延遲. . 證證: 設(shè)設(shè) f 沒有逆序，在沒有逆序，在 f 中具有相同完成時(shí)間的客戶中具有相同完成時(shí)間的客戶i1, i2, , ik 必被連續(xù)安排必被連續(xù)安排. 在這在這k個(gè)客戶中最大延遲是最后一個(gè)客個(gè)客戶中最大延遲是最后一個(gè)客戶，被延遲的時(shí)間是戶，被延遲的時(shí)間是 與與 i1, i2, , ik 的排列次序無關(guān)的排列次序無關(guān). dttkjij 1019交換論證交換論證證明思想：證明思想：從一個(gè)沒有空閑時(shí)間的最優(yōu)解出發(fā)，在不從一個(gè)沒有空閑時(shí)間的最優(yōu)解出發(fā)，在不改變最優(yōu)性的

15、條件下，轉(zhuǎn)變成沒有逆序的解改變最優(yōu)性的條件下，轉(zhuǎn)變成沒有逆序的解. 根據(jù)引理根據(jù)引理 1，這個(gè)解和算法的解具有相同的最大延遲這個(gè)解和算法的解具有相同的最大延遲. 證明要點(diǎn)證明要點(diǎn)(1) 相鄰逆序的存在性：如果一個(gè)最優(yōu)調(diào)度存在逆序，那么相鄰逆序的存在性：如果一個(gè)最優(yōu)調(diào)度存在逆序，那么存在存在 i n 使得使得 (i, i+1) 構(gòu)成一個(gè)逆序構(gòu)成一個(gè)逆序. (2) 交換相鄰的逆序交換相鄰的逆序 i 和和 j ，得到的解的調(diào)度仍舊最優(yōu)，得到的解的調(diào)度仍舊最優(yōu). (3) 每次交換后逆序數(shù)減每次交換后逆序數(shù)減1，至多經(jīng)過，至多經(jīng)過 n(n 1)/2 次交換得到次交換得到一個(gè)沒有逆序的最一個(gè)沒有逆序的最

16、優(yōu)調(diào)度優(yōu)調(diào)度.定理定理4.3 在一個(gè)沒有空閑時(shí)間的最優(yōu)解中，最大延遲是在一個(gè)沒有空閑時(shí)間的最優(yōu)解中，最大延遲是r，如果僅對(duì)具有相鄰逆序的客戶進(jìn)行交換，得到的解的最大如果僅對(duì)具有相鄰逆序的客戶進(jìn)行交換，得到的解的最大延遲不會(huì)超過延遲不會(huì)超過r。20delay(f,i)=stj+ti di delya(f,j) rdelay(f, j)s+ti+tjdj (1) 交換交換 i, j 對(duì)其他客戶的延遲時(shí)間沒影響對(duì)其他客戶的延遲時(shí)間沒影響(2) 交換后不增加交換后不增加 j 的延遲的延遲(3) i 在在 f 的延遲的延遲delay(f,i)小于小于 j 在在 f 的延遲的延遲 delay(f,j),

17、因此小于因此小于f 的最大延遲的最大延遲 rdj di L2i 2得到最優(yōu)解的判定條件得到最優(yōu)解的判定條件定理定理4.6 對(duì)每個(gè)正整數(shù)對(duì)每個(gè)正整數(shù)k，假設(shè)對(duì)所有非負(fù)整數(shù)，假設(shè)對(duì)所有非負(fù)整數(shù) y 有有Gk(y)=Fk(y)且存在且存在 p 和和 滿足滿足 vk+1=pvk , 其中其中0 pw3 v3=pv2 p=3, =1. w3+G2( )=1+1 = 2 pw2=31=3 w3+G2( ) p w2結(jié)論結(jié)論：G3(y)=F3(y), 對(duì)于對(duì)于y=pv3=28，G4(y)F4(y) 274.4 貪心法的典型應(yīng)用貪心法的典型應(yīng)用4.4.1 最優(yōu)前綴碼最優(yōu)前綴碼二元前綴碼二元前綴碼用用0-1字符

18、串作為代碼表示字符，要求任何字符的代碼都字符串作為代碼表示字符，要求任何字符的代碼都不能作為其它字符代碼的前綴不能作為其它字符代碼的前綴非前綴碼的例子非前綴碼的例子 a: 001, b: 00, c: 010, d: 01解碼的歧義，例如字符串解碼的歧義，例如字符串 0100001 解碼解碼1: 01, 00, 001 d, b, a 解碼解碼2: 010, 00, 01 c, b, d 前綴碼的二叉樹及權(quán)值前綴碼的二叉樹及權(quán)值前綴碼前綴碼： 00000, 00001, 0001, 001, 01, 100, 101, 11頻率頻率: 00000: 5%, 000001: 5%, 0001:

19、10%, 001: 15%, 01: 25%, 100: 10%, 101: 10%, 11: 20% 平均的二進(jìn)制位數(shù)平均的二進(jìn)制位數(shù) B=(5+5)5+104 +(15+10+10)3 +(25+20)2/100 =2.85 最優(yōu)前綴碼最優(yōu)前綴碼 權(quán)值權(quán)值B最小最小 )()(1 niiixdxfB最優(yōu)前綴碼問題最優(yōu)前綴碼問題例例4.6 最優(yōu)前綴碼最優(yōu)前綴碼 給定字符集給定字符集 C=x1, x2, , xn和每個(gè)字符和每個(gè)字符的頻率的頻率f(xi), i=1,2,n, 求關(guān)于求關(guān)于C 的一個(gè)最優(yōu)前綴碼的一個(gè)最優(yōu)前綴碼. 算法算法4.4 Huffman(C) 輸入：輸入：C=x1, x2,

20、, xn， f(xi), i=1, 2, , n. 輸出：輸出：Q / /隊(duì)列隊(duì)列 1. n|C| 2. QC /按頻率遞增構(gòu)成隊(duì)列按頻率遞增構(gòu)成隊(duì)列Q 3. for i1 to n 1 do 4. zAllocate-Node() / 生成結(jié)點(diǎn)生成結(jié)點(diǎn) z 5. z.leftQ中最小元中最小元 / 取出取出Q最小元作最小元作z的左兒子的左兒子 6. z.rightQ中最小元中最小元 / 取出取出Q最小元作最小元作z的右兒子的右兒子 7. f(z)f(x)+f(y) 8. Insert(Q,z) / 將將 z 插入插入Q 9. return Q30例如例如 a:45, b:13; c:12;

21、d:16; e:9; f:5 平均位數(shù)：平均位數(shù)：4 (0.05+0.09)+3 (0.16+0.12+0.13)+1 0.45= 2.24編碼：編碼：f-0000, e-0001, d-001, c-010, b011, a-1fe14dcb253055100a5916121345實(shí)例實(shí)例31則則T與與T 的權(quán)之差為的權(quán)之差為其中其中dT(i)為為i 在在T 中的層數(shù)（中的層數(shù)（i 到根的距離）到根的距離） CiCiTTidifidifTBTB0)()() ()(引理引理4.2 設(shè)設(shè)C是字符集，是字符集， c C, f(c)為頻率，為頻率，x, y C, f(x), f(y) 頻率最小，那么

22、存在最優(yōu)二元前綴碼使得頻率最小，那么存在最優(yōu)二元前綴碼使得 x, y 的碼字等長(zhǎng)，的碼字等長(zhǎng)，且僅在最后一位不同且僅在最后一位不同. TTfx fafy fba與與 x 交換交換b與與 y 交換交換yabxTbxyaT算法正確性證明算法正確性證明:引理引理4.232引理引理4.3引理引理4.3 設(shè)設(shè) T 是二元前綴碼所對(duì)應(yīng)的二叉樹，是二元前綴碼所對(duì)應(yīng)的二叉樹， x, y T, x, y是是樹葉兄弟，樹葉兄弟，z 是是 x, y 的父親，令的父親，令T = T x, y, 且令且令 z 的頻率的頻率 f(z) = f(x)+f(y)，T是對(duì)應(yīng)于二元前綴碼是對(duì)應(yīng)于二元前綴碼 C = (C x, y

23、) z 的二叉樹，那么的二叉樹，那么 B(T)=B(T)+f(x)+f(y). )()() ()()()()()()()()()()()()()()()(, ,yfxfTByfxfzdzfidifydyfxdxfidifidifTBTziTiTTTyxiTiTTiT 證證 c C x,y,有有 dT(c) = dT (c) f(c)dT(c)=f(c)dT (c) dT(x) = dT(y) = dT (z) +1. 33定理定理4.7 Haffman 算法對(duì)任意規(guī)模為算法對(duì)任意規(guī)模為n（n 2）的字符集）的字符集C 都都得到關(guān)于得到關(guān)于C 的最優(yōu)前綴碼的二叉樹的最優(yōu)前綴碼的二叉樹. 證明：歸

24、納法證明：歸納法歸納基礎(chǔ)歸納基礎(chǔ) n=2，字符集，字符集C=x1,x2，Huffman算法得到的代碼算法得到的代碼是是0和和1，是最優(yōu)前綴碼，是最優(yōu)前綴碼.歸納步驟歸納步驟 假設(shè)假設(shè)Huffman算法對(duì)于規(guī)模為算法對(duì)于規(guī)模為k 的字符集都得到最的字符集都得到最優(yōu)前綴碼優(yōu)前綴碼. 考慮規(guī)模為考慮規(guī)模為k+1的字符集的字符集C=x1, x2, ., xk+1, 其中其中x1, x2 C是頻率最小的兩個(gè)字符是頻率最小的兩個(gè)字符. 令令 C=(Cx1,x2) z， f(z)=f(x1)+f(x2)根據(jù)歸納假設(shè)，根據(jù)歸納假設(shè)，Huffman算法得到一棵關(guān)于字符集算法得到一棵關(guān)于字符集C 、頻率、頻率f(

25、z)和和f(xi)（i=3,4,.,k+1）的最優(yōu)前綴碼的二叉樹）的最優(yōu)前綴碼的二叉樹T.34把把x1和和 x2作為作為 z 的兒子附加到的兒子附加到T上，得到樹上，得到樹T，那么，那么T是關(guān)于是關(guān)于字符集字符集C=(Cz) x1,x2 的最優(yōu)前綴碼的二叉樹的最優(yōu)前綴碼的二叉樹. 如若不然，存在更優(yōu)的樹如若不然，存在更優(yōu)的樹T*. 根據(jù)引理根據(jù)引理1，其最深層樹葉是，其最深層樹葉是x1, x2，且，且B(T*)B(T). 去掉去掉T*中的中的x1和和x2，根據(jù)引理，根據(jù)引理2，所得，所得二叉樹二叉樹T*滿足滿足 B(T*)B(T*)(f(x1)+f(x2)B(T)(f(x1)+f(x2) =B

26、(T)與與T是一棵關(guān)于是一棵關(guān)于C的最優(yōu)前綴碼的二叉樹矛盾的最優(yōu)前綴碼的二叉樹矛盾. 證明：歸納法證明：歸納法(續(xù)續(xù))zTx2x1Tz Huffman樹應(yīng)用樹應(yīng)用: :文件歸并文件歸并例例4.7 問題：給定一組不同長(zhǎng)度的排好序文件構(gòu)成的集合問題：給定一組不同長(zhǎng)度的排好序文件構(gòu)成的集合 S = f1, , fn 其中其中 fi 表示第表示第 i 個(gè)個(gè)文件含有的項(xiàng)數(shù)文件含有的項(xiàng)數(shù). 使用二分歸并將這些文件使用二分歸并將這些文件歸并成一個(gè)有序的文件歸并成一個(gè)有序的文件. 歸并過程對(duì)應(yīng)于二叉樹：文件為樹葉歸并過程對(duì)應(yīng)于二叉樹：文件為樹葉. fi與與fj 歸并的文件是它歸并的文件是它們的父結(jié)點(diǎn)們的父結(jié)點(diǎn)

27、. 歸并代價(jià)歸并代價(jià)(最多的比較次數(shù)最多的比較次數(shù))：結(jié)點(diǎn)：結(jié)點(diǎn) fi與與 fj 歸并代價(jià)為歸并代價(jià)為 fi+fj 1. 總的代價(jià)：每個(gè)文件總的代價(jià)：每個(gè)文件(樹葉樹葉)的深度乘以文件大小之和再減掉的深度乘以文件大小之和再減掉歸并次數(shù)歸并次數(shù) n 135)1()( nfidiSi36實(shí)例實(shí)例順序歸并順序歸并323110702141187388104192212818701032414973119192Huffman樹歸并樹歸并代價(jià)代價(jià)順序歸并：順序歸并： (21+10+32+41) 3+(18+70) 2 5=483Huffman樹歸并：樹歸并：(10+18) 4+21 3+(70+41+32

28、) 2 5=456實(shí)例：實(shí)例：S = 21,10,32,41,18,70 37無向連通帶權(quán)圖無向連通帶權(quán)圖G=(V,E,W)，w(e) W是邊是邊e的權(quán)的權(quán). G的一棵的一棵生成樹是包含了生成樹是包含了G的所有頂點(diǎn)的樹的所有頂點(diǎn)的樹, 樹中各邊的權(quán)之和稱為樹中各邊的權(quán)之和稱為樹的權(quán)，具有最小權(quán)的生成樹稱為樹的權(quán)，具有最小權(quán)的生成樹稱為G的的最小生成樹最小生成樹. 命題命題4.1 設(shè)設(shè)G是是 n階連通圖，那么階連通圖，那么(1) T是是G 的生成樹當(dāng)且僅當(dāng)?shù)纳蓸洚?dāng)且僅當(dāng) T 有有n1條邊條邊. (2) 如果如果T是是G的生成樹，的生成樹，e T，那么，那么T e含有一個(gè)圈含有一個(gè)圈 (回回 路

29、路). 問題：給定連通帶權(quán)圖問題：給定連通帶權(quán)圖G，求，求G的一棵最小生成樹的一棵最小生成樹. 算法：算法：Prim算法算法和和Kruskal算法算法 4.4.2 最小生成樹最小生成樹12435661556365421243566155636542364251Prim算法算法 算法算法4.5 Prim(G,E,W) 1S1；T 2while V S do 3 從從V S中選擇中選擇 j 使得使得 j 到到 S 中頂點(diǎn)的邊中頂點(diǎn)的邊e的權(quán)最小的權(quán)最小 4 SS j, T T e 39對(duì)步數(shù)歸納對(duì)步數(shù)歸納定理定理4.8 對(duì)于任意對(duì)于任意 k 1, 算法對(duì)算法對(duì) n 階圖得到一棵最小生成樹階圖得到一

30、棵最小生成樹.證明證明 n=2, 只有一條邊，命題顯然為真只有一條邊，命題顯然為真. 假設(shè)對(duì)于假設(shè)對(duì)于n個(gè)頂點(diǎn)的圖算法正確，考慮個(gè)頂點(diǎn)的圖算法正確，考慮n+1個(gè)頂點(diǎn)的圖個(gè)頂點(diǎn)的圖G, G中最小權(quán)邊中最小權(quán)邊 e = i, j，從從G 中中短接短接 i 和和 j，得到圖得到圖G. 根根據(jù)歸納假設(shè)，由算法存在據(jù)歸納假設(shè)，由算法存在G 的最小生成樹的最小生成樹T.令令T=T e, 則則T 是關(guān)于是關(guān)于G 的最小生成樹的最小生成樹. 否則存在否則存在G 的含邊的含邊e 的最小生成樹的最小生成樹T*，W(T*)W(T). (如果如果 e T*, 在在T*中加邊中加邊e，形成回路，形成回路. 去掉回路中任

31、意別的邊去掉回路中任意別的邊所得生成樹的權(quán)仍舊最小所得生成樹的權(quán)仍舊最小). 在在T*中短接中短接 e 得到得到G 的生成的生成樹樹T* e, 且且 W(T* e)=W(T*) w(e)W(T) w(e )=W(T)， 與與T 的最優(yōu)性矛盾的最優(yōu)性矛盾. Kruskal算法正確性證明算法正確性證明算法的實(shí)現(xiàn)與時(shí)間復(fù)雜度算法的實(shí)現(xiàn)與時(shí)間復(fù)雜度數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：建立建立FIND數(shù)組，數(shù)組，F(xiàn)INDi 是結(jié)點(diǎn)是結(jié)點(diǎn) i 的連通分支標(biāo)記的連通分支標(biāo)記. (1) 初始初始FINDi=i. (2) 兩個(gè)連通分支合并，則將較小分支結(jié)點(diǎn)的兩個(gè)連通分支合并，則將較小分支結(jié)點(diǎn)的FIND值更新為值更新為 較大分支

32、的標(biāo)記較大分支的標(biāo)記時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：(1) 每個(gè)結(jié)點(diǎn)至多更新每個(gè)結(jié)點(diǎn)至多更新logn次，建立和更新次，建立和更新FIND數(shù)組的總時(shí)數(shù)組的總時(shí) 間為間為O(nlogn)(2) 算法時(shí)間為算法時(shí)間為 O(mlogm) + O(nlogn) + O(m) = O(mlogn) 邊排序邊排序 FIND數(shù)組數(shù)組 其他其他45給定帶權(quán)有向網(wǎng)絡(luò)給定帶權(quán)有向網(wǎng)絡(luò)G=(V,E,W),每條邊每條邊e=的權(quán)的權(quán)w(e)為非為非負(fù)實(shí)數(shù)，表示從負(fù)實(shí)數(shù)，表示從i到到j(luò) 的距離的距離. 源源點(diǎn)點(diǎn)s V，求從，求從 s 出發(fā)到達(dá)其出發(fā)到達(dá)其它結(jié)點(diǎn)的最短路徑它結(jié)點(diǎn)的最短路徑.Dijkstra算法：算法： x S x V

33、 且從且從 s 到到 x 的最短路徑長(zhǎng)度已知的最短路徑長(zhǎng)度已知初始：初始：S=s ，S=V 時(shí)算法結(jié)束時(shí)算法結(jié)束從從 s 到到 u 相對(duì)于相對(duì)于S 的最短路徑：從的最短路徑：從 s 到到 u且僅經(jīng)過且僅經(jīng)過S 中頂點(diǎn)中頂點(diǎn)的最短路徑的最短路徑distu：從：從 s 到到 u 的相對(duì)于的相對(duì)于S 的最短路徑的長(zhǎng)度的最短路徑的長(zhǎng)度shortu：從：從 s 到到 u 的最短路徑的長(zhǎng)的最短路徑的長(zhǎng)distu shortu 4.4.3 單源最短路徑單源最短路徑46 Dijkstra算法算法算法算法4.7 Dijkstra輸入：帶權(quán)有向圖輸入：帶權(quán)有向圖G=，源點(diǎn)，源點(diǎn)s V輸出：從輸出：從 s 到每個(gè)結(jié)

34、點(diǎn)到每個(gè)結(jié)點(diǎn) i 的最短路徑的最短路徑 1. Ss 2. dists0 3. for i V s do 4. distiw(s,i) / 如果如果s到到i沒有邊沒有邊, w(s,i)= 5. while V S do 6. 從從V S中取出具有相對(duì)中取出具有相對(duì)S的最短路徑的頂點(diǎn)的最短路徑的頂點(diǎn) j 7. SS j; 8. for i V S do 9. if distj+w(j,i)disti 10. then disti distj+w(j,i) / 更新更新disti47S=1, dist1=0 dist2=10, dist6=3 dist3=dist4=dist5= 實(shí)例實(shí)例10416

35、54337376122510416543373761225S=1,6, dist1=0, dist6=3 dist2=5, dist4=9, dist5=4 dist3= 輸入：輸入：G=，源點(diǎn)，源點(diǎn) 1V=1, 2, 3, 4, 5, 648S=1,6,5, dist1=0, dist6=3, dist5=4 dist2=5, dist4=9, dist3= 實(shí)例（續(xù)）實(shí)例（續(xù)）1041654337376122510416543373761225S=1,6,5,2, dist1=0, dist6=3, dist5=4 dist2=5 dist3=12 dist4=9 49S=1,6,5,2,

36、4, dist1=0, dist6=3, dist5=4 dist2=5, dist4=9, dist3=12 實(shí)實(shí) 例（續(xù)）例（續(xù)）1041654337376122510416543373761225S=1,6,5,2,4,3, dist1=0, dist6=3, dist5=4 dist2=5, dist4=9 dist3=12 解：解：short1=0, short2=5,short3=12, short4=9，short5=4, short6=3. 50 算法正確性證明算法正確性證明定理定理4.10 當(dāng)算法進(jìn)行到第當(dāng)算法進(jìn)行到第 k 步時(shí)，對(duì)于步時(shí)，對(duì)于S 中每個(gè)結(jié)點(diǎn)中每個(gè)結(jié)點(diǎn) i，

37、disti = shorti 歸納基礎(chǔ)歸納基礎(chǔ) k=1, S=s, dists=shorts=0, 命題為真命題為真.歸納步驟歸納步驟 假設(shè)命題對(duì)于假設(shè)命題對(duì)于k 為真為真. 考慮考慮 k+1步步, 選擇頂點(diǎn)選擇頂點(diǎn)v (邊邊u,v). 假若存在另一條假若存在另一條 s-v 路徑路徑 L (綠色綠色)，最后一次出，最后一次出S 的的頂點(diǎn)為頂點(diǎn)為 x, 在這次從在這次從S 中出來后中出來后經(jīng)過經(jīng)過V S 的第一個(gè)頂點(diǎn)為的第一個(gè)頂點(diǎn)為 y.時(shí)間復(fù)雜度時(shí)間復(fù)雜度 T(n)=O(n2)distv=shortvsuxyvLSdistv disty /v先被選先被選 disty+d(y,v) L 51 貪

38、心法小結(jié)貪心法小結(jié)(1) 適用于組合優(yōu)化問題，適用于組合優(yōu)化問題， 求解過程是多步判斷求解過程是多步判斷. 判斷的依據(jù)判斷的依據(jù)是局部最優(yōu)策略，使目標(biāo)值達(dá)到最大是局部最優(yōu)策略，使目標(biāo)值達(dá)到最大(或最小或最小)，與前面的，與前面的子問題計(jì)算結(jié)果無關(guān)子問題計(jì)算結(jié)果無關(guān). (2) 局部最優(yōu)策略的選擇是算法正確性的關(guān)鍵局部最優(yōu)策略的選擇是算法正確性的關(guān)鍵. (3) 正確性證明方法：數(shù)學(xué)歸納法、交換論證正確性證明方法：數(shù)學(xué)歸納法、交換論證. 使用數(shù)學(xué)歸納使用數(shù)學(xué)歸納 法主要通過對(duì)算法步數(shù)或者問題規(guī)模進(jìn)行歸納法主要通過對(duì)算法步數(shù)或者問題規(guī)模進(jìn)行歸納. 如果要證如果要證 明貪心策略是錯(cuò)誤的，只需舉出反例明貪

39、心策略是錯(cuò)誤的，只需舉出反例. (4) 自頂向下求解，通過選擇將問題歸約為小的子問題自頂向下求解，通過選擇將問題歸約為小的子問題. (5) 如果貪心法得不到最優(yōu)解，可以對(duì)問題的輸入進(jìn)行分析如果貪心法得不到最優(yōu)解，可以對(duì)問題的輸入進(jìn)行分析 或者估計(jì)算法的近似比或者估計(jì)算法的近似比. (6) 如果對(duì)原始數(shù)據(jù)排序之后，貪心法往往是一輪處理，時(shí)如果對(duì)原始數(shù)據(jù)排序之后，貪心法往往是一輪處理，時(shí) 間復(fù)雜度和空間復(fù)雜度低間復(fù)雜度和空間復(fù)雜度低. 52 不同算法策略特點(diǎn)不同算法策略特點(diǎn)(1) 貪心法：貪心法：通過局部最優(yōu)決策到達(dá)全局最優(yōu)決策通過局部最優(yōu)決策到達(dá)全局最優(yōu)決策 (2) 遞推法：遞推法：由當(dāng)前問題的

40、逐步解決從而得到整個(gè)問題的解，它依賴信由當(dāng)前問題的逐步解決從而得到整個(gè)問題的解，它依賴信息間遞推關(guān)系，由小到大。息間遞推關(guān)系，由小到大。(3) 遞歸法：遞歸法：利用大問題與其子問題間的遞推關(guān)系。將大問題分解成規(guī)利用大問題與其子問題間的遞推關(guān)系。將大問題分解成規(guī)模較小的問題，然后從小問題的解構(gòu)造出大問題的解。模較小的問題，然后從小問題的解構(gòu)造出大問題的解。 (4) 枚舉法：枚舉法：逐一嘗試。逐一嘗試。(5) 遞歸回溯法：遞歸回溯法：通過遞歸嘗試遍歷問題各個(gè)可能解的通路，不同時(shí)通過遞歸嘗試遍歷問題各個(gè)可能解的通路，不同時(shí)回溯上一步?；厮萆弦徊?。 (6) 分治法：分治法：復(fù)雜問題分解成獨(dú)立子問題并解

41、決，再將它們的解合成。復(fù)雜問題分解成獨(dú)立子問題并解決，再將它們的解合成。(7) 動(dòng)態(tài)規(guī)劃法：動(dòng)態(tài)規(guī)劃法：保留多個(gè)階段的決策結(jié)果，為以后每個(gè)階段提供決保留多個(gè)階段的決策結(jié)果，為以后每個(gè)階段提供決策；問題不能分為獨(dú)立階段，且符合最優(yōu)化原理；解決子問題冗余。策；問題不能分為獨(dú)立階段，且符合最優(yōu)化原理；解決子問題冗余。53 算法策略間的關(guān)聯(lián)算法策略間的關(guān)聯(lián)(1)對(duì)問題進(jìn)行分解的算法策略：對(duì)問題進(jìn)行分解的算法策略：分治法、動(dòng)態(tài)規(guī)劃分治法、動(dòng)態(tài)規(guī)劃(2)多階段逐步解決問題的策略：多階段逐步解決問題的策略：貪心法、遞推法、遞貪心法、遞推法、遞歸法、動(dòng)態(tài)規(guī)劃歸法、動(dòng)態(tài)規(guī)劃(3)全面逐一嘗試：全面逐一嘗試：枚舉

42、法、遞歸回溯法枚舉法、遞歸回溯法整數(shù)的分劃問題整數(shù)的分劃問題( (較復(fù)雜的遞歸設(shè)計(jì)較復(fù)雜的遞歸設(shè)計(jì)) )對(duì)于一個(gè)正整數(shù)對(duì)于一個(gè)正整數(shù)n n的分劃就是把的分劃就是把n n寫成一系列正整數(shù)之和的表達(dá)寫成一系列正整數(shù)之和的表達(dá)式。例如，對(duì)于正整數(shù)式。例如，對(duì)于正整數(shù)n=6n=6，它可以分劃為：它可以分劃為： 6 6 5+1 5+1 4+2, 4+1+1 4+2, 4+1+1 3+3, 3+2+1, 3+1+1+1 3+3, 3+2+1, 3+1+1+1 2+2, 2+2+1+1, 2+1+1+1+1 2+2, 2+2+1+1, 2+1+1+1+1 1+1+1+1+1+11+1+1+1+1+1 根據(jù)例

43、子發(fā)現(xiàn)根據(jù)例子發(fā)現(xiàn)“包括第一行以后的數(shù)據(jù)不超過包括第一行以后的數(shù)據(jù)不超過6 6，包括，包括第二行的數(shù)據(jù)不超過第二行的數(shù)據(jù)不超過5 5，第六行的數(shù)據(jù)不超過，第六行的數(shù)據(jù)不超過1”1”。 因此，定義一個(gè)函數(shù)因此，定義一個(gè)函數(shù)Q(n,m)Q(n,m)，表示整數(shù)表示整數(shù)n n的的“任何被加任何被加數(shù)都不超過數(shù)都不超過m”m”的分劃的數(shù)目，的分劃的數(shù)目，n n的所有分劃的數(shù)目的所有分劃的數(shù)目P(n)=Q(n,n)P(n)=Q(n,n)。模型建立模型建立 一般地一般地Q(n,mQ(n,m) )有以下遞歸關(guān)系：有以下遞歸關(guān)系： 1)Q(n,n)=1+Q(n,n-1) 1)Q(n,n)=1+Q(n,n-1)

44、（m=nm=n）Q(n,n-1)Q(n,n-1)表示表示n n的所有其他分劃，即最大被加數(shù)的所有其他分劃，即最大被加數(shù)m=n-1m=n-1的劃分。的劃分。2)Q(n,m)=Q(n,m-1)+Q(n-m,m) (mn)2)Q(n,m)=Q(n,m-1)+Q(n-m,m) (m1/27/81/2， 7/8-1/21/37/8-1/21/3， 7/8-1/2-1/3=1/247/8-1/2-1/3=1/24。過程如下：過程如下： 1)1)找最小的找最小的n n（也就是最大的埃及分?jǐn)?shù)），使分?jǐn)?shù)也就是最大的埃及分?jǐn)?shù)），使分?jǐn)?shù)f1/nf1/n； 2)2)輸出輸出1/n1/n； 3)3)計(jì)算計(jì)算f=f-1/

45、nf=f-1/n； 4)4)若此時(shí)的若此時(shí)的f f是埃及分?jǐn)?shù)，輸出是埃及分?jǐn)?shù)，輸出f,f,算法結(jié)束算法結(jié)束, ,否則返回否則返回1 1）。）。 數(shù)學(xué)模型數(shù)學(xué)模型 記真分?jǐn)?shù)記真分?jǐn)?shù)F=A/BF=A/B；對(duì)；對(duì)B/AB/A進(jìn)行整除運(yùn)算進(jìn)行整除運(yùn)算, ,商為商為D, D, 余數(shù)為余數(shù)為0 0K KA A，它們之間的關(guān)系及導(dǎo)出關(guān)系如下：它們之間的關(guān)系及導(dǎo)出關(guān)系如下：( (例：例：A=7,B=8 = D=1,K=1)A=7,B=8 = D=1,K=1) B=AB=A* *D+KD+K，B/A=D+K/AB/A=D+K/AD+1D+1，A/BA/B1/(D+1)1/(D+1)，記，記C=D+1C=D+1。

46、 這樣我們就找到了分?jǐn)?shù)這樣我們就找到了分?jǐn)?shù)F F所包含的所包含的“最大的最大的”埃及分?jǐn)?shù)就是埃及分?jǐn)?shù)就是1/C1/C。進(jìn)一步計(jì)算：進(jìn)一步計(jì)算： A/B-1/C=A/B-1/C=（A A* *C-BC-B）/B/B* *C C 也就是說繼續(xù)要解決的是有關(guān)也就是說繼續(xù)要解決的是有關(guān)分子為分子為A=AA=A* *C-BC-B, ,分母為分母為B=BB=B* *C C的的問題。問題。 算法設(shè)計(jì)算法設(shè)計(jì) 由以上數(shù)學(xué)模型，真正的由以上數(shù)學(xué)模型，真正的算法過程算法過程如下：如下： 1)1)設(shè)某個(gè)真分?jǐn)?shù)的分子為設(shè)某個(gè)真分?jǐn)?shù)的分子為A(1A(1），），分母為分母為B B； 2)2)把把B B除以除以A A的商的

47、整數(shù)部分加的商的整數(shù)部分加1 1后的值作為埃及后的值作為埃及 分?jǐn)?shù)的一個(gè)分母分?jǐn)?shù)的一個(gè)分母C;C; 3) 3)輸出輸出1/C1/C； 4)4)將將A A乘以乘以C C減去減去B B作為新的作為新的A A； 5)5)將將B B乘以乘以C C作為新的作為新的B B； 6)6)如果如果A A大于大于1 1且能整除且能整除B,B,則最后一個(gè)分母為則最后一個(gè)分母為B/AB/A； 7)7)如果如果A A1,1,則最后一個(gè)分母為則最后一個(gè)分母為B;B;否則轉(zhuǎn)步驟否則轉(zhuǎn)步驟(2).(2). 例：例：7/8=1/2+1/3+1/247/8=1/2+1/3+1/24的解題步驟：的解題步驟： 同樣用變量同樣用變量A

48、 A表示分子，變量表示分子，變量B B表示分母；表示分母； C=8/7+1=2 C=8/7+1=2 / /說明說明7/81/27/81/2， 打印打印1/21/2 A=7A=7* *2-8=62-8=6，B=BB=B* *C=16C=16/在計(jì)算在計(jì)算7/8-1/2=(77/8-1/2=(7* *2-8)/(72-8)/(7* *2)=6/16=A/B2)=6/16=A/B C=16/6+1=3 C=16/6+1=3 / /說明說明16/61/316/61/3，打印，打印1/31/3 A=6A=6* *3-16=2,B=B3-16=2,B=B* *C=16C=16* *3=483=48/在計(jì)算

49、在計(jì)算6/16-1/3=(66/16-1/3=(6* *3-16)/(163-16)/(16* *3)=2/48=A/B3)=2/48=A/B A1 A1但但B/AB/A為整數(shù)為整數(shù)2424，打印，打印1/24 1/24 結(jié)束結(jié)束. .算法實(shí)現(xiàn)算法實(shí)現(xiàn)main（）（） int a,b,c; print(“input element”); input(a); print(“input denominator”); input(b); if(ab) print(“input error”); else if (a=1 or b mod a=0) print( a, /,b, = 1, /,b/a)

50、; else while(a1) c = b / a + 1 a = a * c b；b = b *c； print( 1/,c); if (b mod a =0 ) print (+1/; b / a); a=1; if( a 1) print(+); 取數(shù)游戲取數(shù)游戲 有2個(gè)人輪流取2n個(gè)數(shù)中的n個(gè)數(shù)，取數(shù)之和大者為勝。請(qǐng)編寫算法，讓先取數(shù)者勝，模擬取數(shù)過程。 問題分析 算法設(shè)計(jì) 算法說明 算法分析 問題分析問題分析 這個(gè)游戲一般假設(shè)取數(shù)者只能看到這個(gè)游戲一般假設(shè)取數(shù)者只能看到2n2n個(gè)數(shù)中兩邊的數(shù)個(gè)數(shù)中兩邊的數(shù), ,用貪婪算法的情況用貪婪算法的情況: : 若一組數(shù)據(jù)為：若一組數(shù)據(jù)為：6,

51、16,27,6,12,9,2,11,6,56,16,27,6,12,9,2,11,6,5。用貪婪策。用貪婪策略每次兩人都取兩邊的數(shù)中較大的一個(gè)數(shù)略每次兩人都取兩邊的數(shù)中較大的一個(gè)數(shù), ,先取者勝先取者勝. .以以A先先取為例：取為例： 取數(shù)結(jié)果為：取數(shù)結(jié)果為： A 6,27,12,5,11=61 A 6,27,12,5,11=61 勝勝 B 16,6,9,6,2=39B 16,6,9,6,2=39 但若選另一組數(shù)據(jù)：但若選另一組數(shù)據(jù)：16,27,7,12,9,2,11,616,27,7,12,9,2,11,6。仍都用貪婪。仍都用貪婪算法，先取者算法，先取者A A敗。敗。 取數(shù)結(jié)果為：取數(shù)結(jié)果為

52、： A 16,7,9,11=43A 16,7,9,11=43 B 27,12,6,2=47 B 27,12,6,2=47 勝勝 其實(shí)，若我們只能看到兩邊的數(shù)據(jù)，則此題無論其實(shí)，若我們只能看到兩邊的數(shù)據(jù)，則此題無論先取還先取還是后取都無必勝的策略是后取都無必勝的策略。這時(shí)一般的策略是用近似貪婪算法。這時(shí)一般的策略是用近似貪婪算法。 但但若取數(shù)者能看到全部若取數(shù)者能看到全部2n2n個(gè)數(shù)個(gè)數(shù)，則此問題可有一些簡(jiǎn)單，則此問題可有一些簡(jiǎn)單的方法，有的雖不能保證所取數(shù)的和是最大，但確是一個(gè)先的方法，有的雖不能保證所取數(shù)的和是最大，但確是一個(gè)先取者必勝的策略。取者必勝的策略。 數(shù)學(xué)模型建立：數(shù)學(xué)模型建立：N

53、個(gè)數(shù)排成一行，我們給這個(gè)數(shù)排成一行，我們給這N個(gè)數(shù)從左到右編號(hào)，個(gè)數(shù)從左到右編號(hào)，依次為依次為1，2，N，因?yàn)橐驗(yàn)镹為偶數(shù)，又因?yàn)槭俏覀兿热?shù)，計(jì)為偶數(shù)，又因?yàn)槭俏覀兿热?shù)，計(jì)算機(jī)后取數(shù)，所以一開始我們既可以取到一個(gè)奇編號(hào)的數(shù)（最算機(jī)后取數(shù)，所以一開始我們既可以取到一個(gè)奇編號(hào)的數(shù)（最左邊編號(hào)為左邊編號(hào)為1的數(shù)）又可以取到一個(gè)偶編號(hào)的數(shù)（最右邊編號(hào)的數(shù)）又可以取到一個(gè)偶編號(hào)的數(shù)（最右邊編號(hào)為為N的數(shù)）。的數(shù)）。 如果我們第一次取奇編號(hào)（編號(hào)為如果我們第一次取奇編號(hào)（編號(hào)為1）的數(shù)，則接著計(jì)算機(jī)）的數(shù)，則接著計(jì)算機(jī)只能取到偶編號(hào)（編號(hào)為只能取到偶編號(hào)（編號(hào)為2或或N）的數(shù)；的數(shù)； 如果我們第一次取

54、偶編號(hào)（編號(hào)為如果我們第一次取偶編號(hào)（編號(hào)為N）的數(shù)，則接著計(jì)算機(jī)的數(shù)，則接著計(jì)算機(jī)只能取到奇編號(hào)（編號(hào)為只能取到奇編號(hào)（編號(hào)為1或或N-1）的數(shù)；的數(shù)； 即無論我們第一次是取奇編號(hào)的數(shù)還是取偶編號(hào)的數(shù)，接著即無論我們第一次是取奇編號(hào)的數(shù)還是取偶編號(hào)的數(shù)，接著計(jì)算機(jī)只能取到另一種編號(hào)（偶編號(hào)或奇編號(hào)）的數(shù)。計(jì)算機(jī)只能取到另一種編號(hào)（偶編號(hào)或奇編號(hào)）的數(shù)。 這是對(duì)第一個(gè)回合的分析，顯然對(duì)以后整個(gè)取數(shù)過程都適這是對(duì)第一個(gè)回合的分析，顯然對(duì)以后整個(gè)取數(shù)過程都適用。也就是說，我們能夠控制讓計(jì)算機(jī)自始自終只取一種編號(hào)用。也就是說，我們能夠控制讓計(jì)算機(jī)自始自終只取一種編號(hào)的數(shù)。這樣，我們只要比較奇編號(hào)數(shù)之

55、和與偶編號(hào)數(shù)之和誰大，的數(shù)。這樣，我們只要比較奇編號(hào)數(shù)之和與偶編號(hào)數(shù)之和誰大，以決定最開始我們是取奇編號(hào)數(shù)還是偶編號(hào)數(shù)即可。（如果奇以決定最開始我們是取奇編號(hào)數(shù)還是偶編號(hào)數(shù)即可。（如果奇編號(hào)數(shù)之和與偶編號(hào)數(shù)之和同樣大，我們第一次可以任意取數(shù)，編號(hào)數(shù)之和與偶編號(hào)數(shù)之和同樣大，我們第一次可以任意取數(shù)，因?yàn)楫?dāng)兩者所取數(shù)和相同時(shí)，先取者為勝。因?yàn)楫?dāng)兩者所取數(shù)和相同時(shí)，先取者為勝。算法設(shè)計(jì)：算法設(shè)計(jì)：有了以上建立的高效數(shù)學(xué)模型，算法就很簡(jiǎn)單了，算有了以上建立的高效數(shù)學(xué)模型，算法就很簡(jiǎn)單了，算法只需要分別計(jì)算一組數(shù)的奇數(shù)位和偶數(shù)位的數(shù)據(jù)之和，然后就法只需要分別計(jì)算一組數(shù)的奇數(shù)位和偶數(shù)位的數(shù)據(jù)之和，然后就先

56、了取數(shù)者就可以確定必勝的取數(shù)方式了。先了取數(shù)者就可以確定必勝的取數(shù)方式了。以下面一排數(shù)為例：以下面一排數(shù)為例：1 2 3 10 5 6 7 8 9 4奇編號(hào)數(shù)之和為奇編號(hào)數(shù)之和為25（=1+3+5+7+9），小于偶編號(hào)數(shù)之和為），小于偶編號(hào)數(shù)之和為30（=2+10+6+8+4）。我們第一次?。?。我們第一次取4，以后，計(jì)算機(jī)取哪邊的數(shù)，以后，計(jì)算機(jī)取哪邊的數(shù)我們就取哪邊的數(shù)（如果計(jì)算機(jī)取我們就取哪邊的數(shù)（如果計(jì)算機(jī)取1，我們就取，我們就取2；如果計(jì)算機(jī)取；如果計(jì)算機(jī)取9，我們就取，我們就取8）。這樣可以保證我們自始自終取到偶編號(hào)的數(shù)，）。這樣可以保證我們自始自終取到偶編號(hào)的數(shù)，而計(jì)算機(jī)自始自終取

57、到奇編號(hào)的數(shù)。而計(jì)算機(jī)自始自終取到奇編號(hào)的數(shù)。背包問題背包問題 給定給定n種物品和一個(gè)容量為種物品和一個(gè)容量為C的背包，物的背包，物品品i的重量是的重量是wi，其價(jià)值為其價(jià)值為vi，背包問題是如何背包問題是如何選擇裝入背包的物品，使得裝入背包中物品的選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大總價(jià)值最大? 于是，背包問題歸結(jié)為尋找一個(gè)滿足約束條于是，背包問題歸結(jié)為尋找一個(gè)滿足約束條件式件式1-1，并使目標(biāo)函數(shù)式，并使目標(biāo)函數(shù)式1-2達(dá)到最大的解向量達(dá)到最大的解向量X=(x1, x2, , xn)。設(shè)設(shè)xi表示物品表示物品i裝入背包的情況，根據(jù)問題的要求，裝入背包的情況，根據(jù)問題的要求，有

58、如下約束條件和目標(biāo)函數(shù)：有如下約束條件和目標(biāo)函數(shù)： )1 (101nixCxwiniii（式（式1-1）niiixv1max（式（式1-2）至少有三種看似合理的貪心策略： （1）選擇價(jià)值最大的物品，因?yàn)檫@可以盡可能快地增加背包的總價(jià)值。但是，雖然每一步選擇獲得了背包價(jià)值的極大增長(zhǎng)，但背包容量卻可能消耗得太快，使得裝入背包的物品個(gè)數(shù)減少，從而不能保證目標(biāo)函數(shù)達(dá)到最大。 （2）選擇重量最輕的物品，因?yàn)檫@可以裝入盡可能多的物品，從而增加背包的總價(jià)值。但是，雖然每一步選擇使背包的容量消耗得慢了，但背包的價(jià)值卻沒能保證迅速增長(zhǎng)，從而不能保證目標(biāo)函數(shù)達(dá)到最大。 （3）選擇單位重量?jī)r(jià)值最大的物品，在背包價(jià)值

59、增長(zhǎng)和背包容量消耗兩者之間尋找平衡。 應(yīng)用第三種貪心策略，每次從物品集合中選擇單位重量?jī)r(jià)值最大的物品，如果其重量小于背包容量，就可以把它裝入，并將背包容量減去該物品的重量，然后我們就面臨了一個(gè)最優(yōu)子問題它同樣是背包問題，只不過背包容量減少了，物品集合減少了。因此背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 60 120 50 背包 180 190 200(a) 三個(gè)物品及背包 (b) 貪心策略1 (c) 貪心策略2 (d) 貪心策略3 50 30 10 20 20 3020/30 20 1010/20 30 10例如，有3個(gè)物品，其重量分別是20, 30, 10，價(jià)值分別為60, 120, 50，背包的容量為

60、50，應(yīng)用三種貪心策略裝入背包的物品和獲得的價(jià)值如圖所示。 設(shè)背包容量為C，共有n個(gè)物品，物品重量存放在數(shù)組wn中，價(jià)值存放在數(shù)組vn中，問題的解存放在數(shù)組xn中。 算法算法背包問題背包問題1改變數(shù)組改變數(shù)組w和和v的排列順序，使其按單位重量?jī)r(jià)值的排列順序，使其按單位重量?jī)r(jià)值vi/wi降序排列；降序排列；2將數(shù)組將數(shù)組xn初始化為初始化為0； /初始化解向量初始化解向量3i=1; 4循環(huán)直到循環(huán)直到(wiC) 4.1 xi=1; /將第將第i個(gè)物品放入背包個(gè)物品放入背包 4.2 C=C-wi; 4.3 i+;5. xi=C/wi;算法的時(shí)間主要消耗在將各種物品依其單位重量的價(jià)值從算法的時(shí)間主要