算法課后作業(yè)參考答案第四章

1、第四章 貪心算法算法分析題：課后作業(yè)4-1（此為第三版書的 4-1 題）在活動安排問題中，還可以有其它的貪心選擇方案，但并不能保證產(chǎn)生最優(yōu)解。給出一個例子，說明若選擇具有最短時段的相容活動作為貪心選擇，得不到最優(yōu)解。若選擇覆蓋未選擇活動最少的相容活動作為貪心選擇，也得不到最優(yōu)解。參考解答：這兩個貪心選擇方案都不能得到最優(yōu)解的，反例在上課的課件上?；顒酉盗校鹤顑?yōu)解1,2,3,4，4 個相容活動。若選擇具有最短時段的相容活動作為貪心選擇，則選擇為1,4,5。只有 3 個相容活動，不是最優(yōu)解。若選擇覆蓋未選擇活動最少的相容活動作為貪心選擇，必初選 5，5 一旦選中，最多只能再選兩個。最多只有 3 個

2、相容活動，也不是最優(yōu)解。4-3（此為第三版書的 4-3 題）在 0-1 背包問題中，各物品依重量遞增排列時，其價值恰好遞減排列。對這個特殊的 0-1 背包問題，設(shè)計一個有效算法找出最優(yōu)解，并證明算法的正確性。參考解答：共 n 件物品， w，背包容量 C。根據(jù)題意，不妨設(shè)：0 w1 w2 wn ， v1 v2 vn 0v： iwivi1,1 i n 1 wi11、算法描述當物品未排好序時，將物品按照重量遞增序排序（其實，也就是按照價值遞減序排序），當物品已按重量排好序了，此步略過；按照前一步排序后的物品順序，依次挑選物品進背包，直到裝不進背包為止。這個算法第一步需要 O(nlogn)，第二步需要

3、 O(n)。因此整個算法需要 O(nlogn)的計算時間。2、算法正確性證明先此特殊 0-1 背包問題的貪心選擇性質(zhì)：當 w1 C 時，問題無解。當 w1 C 時，此時的貪心選擇性質(zhì)就轉(zhuǎn)化為證明：存在這個特殊 0-1 背包問題的一個最優(yōu)解 S 1,2,., n，S 為 n 個物品集合的一個子集，且1 S 。若 S 1,2,., n 是特殊 0-1 背包問題的一個最優(yōu)解，且1 S ，對 i S ， 令Q S 1 i，且有 w1 wi 。則： wj wj w1 wi CjQ jS 因此， Q S 1 i 是此特殊 0-1 背包問題的一個可行解。另外，vj vj v1 vi vj（1）jQjS jS

4、 又由于之前假設(shè) S 是一個最優(yōu)解，故vj v j（2）jSjQ 結(jié)合不等式（1）和不等式（2），有v j vj ，故Q S 1 i 也是一個 最優(yōu)jSjQ 解，又Q 滿足貪心選擇性質(zhì)，因此Q 是一個滿足貪心選擇性質(zhì)的最優(yōu)解，又由于所有的 0-1背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（這一性質(zhì)在書上 P106 有敘述，這里不再累述），因此貪心算法的正確性得證。4-2 參考解答：最優(yōu)裝載問題若推廣至兩艘船（第一艘船和第二艘船載重量為 c1 和 c2），要看這問題怎么問？這個問題分析起來其實很復雜啊。在 OJ 系統(tǒng)上已經(jīng)增加了一題“17097 兩艘船的裝載問題”，用測試數(shù)據(jù)對這個問題來舉例說明。點評：在大家作

5、業(yè)中僅看見很少的幾位同學對這道題有展開分析的，大多數(shù)同學都千篇一律的回答，比如“不能采用貪心算法”，“應(yīng)該盡可能將第一艘船裝滿”等這樣的回答。n i i1c ，是否有方案能將 n 個箱子裝上兩艘船？（1）n 個箱子，且n ic ，所以，兩艘船上必然有剩余空間，這完全就是書上 5.2 這個例子，因為i1那讓部分的箱子上第一艘船且盡可能接近 c1，使第一艘船剩余空間盡可能?。吹谝凰掖M可能滿但不超過 c1），剩下的集裝箱再裝上第二艘船，如果可以裝上第二艘船，則可以將這 n 個箱子裝上兩艘船。但若剩下的箱子不能全裝上第二艘船，請大家思考一下，是否就可以說明這個問題無滿足的方案？我認為應(yīng)該再嘗試一下

6、“先盡可能把第二艘船裝滿（最接近 c2），剩下看看能否裝上第一艘船？”（2）n 個箱子，能否盡可能多的將箱子裝上兩艘船？（指所有裝上船的箱子的數(shù)量），如何能裝上盡可能多的箱子呢？若還按照較輕的箱子先裝這樣的貪心算法就不一定能產(chǎn)生最優(yōu)解了。比如：若 10件箱子，分別：10 10 10 15 15 15 20 20 30 40，兩艘船載重量分別為 70 和 50，若還按較輕者先裝，則 10+10+10+15+15=60 裝入第一艘船，15+20=35 裝入第二艘船，共 7 個箱子。而這個問題的最優(yōu)解，有多種方法可以裝到 8 個箱子，比如，10+10+10+15+20=65 裝入第一艘船，15+15

7、+20=50 裝入第二艘船去，則總共裝上 8個箱子。若盡可能將第一艘船裝滿這個策略也是的，比如，14 個箱子，分別：54 53 2 22 2 2 2 2 2 2 2 2 2，兩艘船載重量分別為：55 和 54。若盡可能將第一艘船裝滿，則選擇 53+2 兩個箱子裝入第一艘船，54 裝入第二艘船，共 3 個箱子。而這個問題有更好的解：54（上第一艘）+ 12*2（上第二艘），共 13 個箱子。有同學會想，是否能變換一下：先將第二艘船裝滿再盡可能滿的裝第一艘船，和之前先將第一艘船裝滿再盡可能滿的裝第二艘船，這兩種情況進行比較，取裝的較好的這種。這樣想法也是的，還是前面 14 個箱子的例子，分別：54

8、 53 2 2 22 2 2 2 2 2 2 2 2，兩艘船載重量分別為：55 和 54。倒過來先裝第二艘船再裝第一艘船的話，也是只能上 3 個箱子，而這個問題最優(yōu)的 13 個箱子，是這兩種裝法都達不到的?？偨Y(jié)一句：要獲得上船的箱子總數(shù)量盡可能多，不能采用先盡可能將第一艘船裝滿再盡可能裝滿第二艘船，倒過來先裝第二艘船也，或者兩種情況求較大，這樣也。這條路走不通了。當然，這里沒有限制所有箱子重量和要小于等于兩艘船的載重量 c1+c2 之和。若如前有這個條件，大家考慮一下是否可行，這里我沒有繼續(xù)考慮下去了。（3）n 個箱子，能否盡可能重的將箱子裝上兩艘船？（指所有裝上船的箱子的重量和）此題若是變一

9、下問題的求解目標：n 個重量可能不等的箱子，如何裝上兩艘船，使得裝上船箱子的重量之和為最大？考慮一下，如果也盡可能讓第一艘船裝滿或盡可能讓第二艘船裝滿，這樣能達到最優(yōu)目標嗎？若 4 件箱子，分別：10 40 20 25，兩艘船，載重量分別為：55 和 30。若先盡可能將第一艘船裝滿，選擇 10+20+25 這幾個箱子裝入第一艘船，則第二艘船最多裝 0。共 10+20+25=55 裝入兩艘船。若先盡可能將第二艘船裝滿，選擇 10+20 這幾個箱子裝入第二艘船，則第一艘船最多裝 40。共 40+10+20=70 裝入兩艘船。而這個問題有更優(yōu)解：10+40 裝入第一艘船，而 25 裝入第二艘船，共

10、10+40+25=75裝入兩艘船?？偨Y(jié)一句：以上的反例，說明這個問題考慮先將第一艘船盡可能裝滿，或考慮先將第二艘船盡可能裝滿，再或者兩者取較優(yōu)，這些考慮都。那（2）和（3）問題如何求解？其實無論最優(yōu)目標是盡可能多還是盡可能重，都可把每個箱子視為三種狀態(tài)。那就是該箱子不選（狀態(tài)為 0）？或是放上第一艘船（狀態(tài)為 1）？還是放上第二艘船（狀態(tài)為 2）？轉(zhuǎn)化為求解問題解向量（x1, x2, , xn），xi0, 1, 2，0代表不選即既不上第一艘船也不上第二艘船，1 代表裝上第一艘船，2 代表裝上第二艘船。那這個解空間樹就是一棵完全三叉樹，采用深度優(yōu)先的回溯算法可無遺漏地找到盡可能多或是盡可能重的最

11、優(yōu)解，這樣搜索一定可以找到最優(yōu)解。4-3 參考解答：若字符 ah 出現(xiàn)的頻率恰好是前 8 個 Fibonacci 數(shù)，它們的 Haffman 編碼樹如下圖所示。0101hg0100111fe0d1bc0a將結(jié)果推廣到 n 個字符頻率恰好是前 n 個 Fibonacci 數(shù)，則相應(yīng)的 Haffman 編碼樹和上圖類似，樹的深度為 n-1，第一第二個字符編碼長度為 n-1，這可以根據(jù) Haffman 樹的構(gòu)造和數(shù)學歸納法證明得到。第四章 貪心算法算法實現(xiàn)題：4-6 實現(xiàn)：最短服務(wù)時間優(yōu)先。4-9 實現(xiàn)最遠：優(yōu)先。4-10 實現(xiàn)：每次覆蓋盡可能多的點。4-11 實現(xiàn)從數(shù)的：到低位掃描，遞減區(qū)間的首字

12、符優(yōu)先考慮刪除掉。4-14 實現(xiàn)：最大費用：每次選最大的 2 個元素合并最小費用：每次選最小的 k 個元素合并貪心的方法如下：保證每次選兩堆最多的，合并直至只剩一堆為止，能獲得最大得分；這個和 huffman 樹構(gòu)造是相同的，不再詳述！保證每次選 k 堆最少的，合并直至只剩一堆為止，能獲得最小得分。這個是多元 huffman 樹的構(gòu)造。要注意的是：在合并之前，若 n%(k-1)!=1，說明合并到最后一輪時，剩下不是 k 堆（而是比 k 堆少），這樣算的并不是最小得分，而必須在合并之前添加若干個為 0 的虛擬堆，目的為湊成的堆數(shù)保證每次都能有 k 堆合并（包括最后一次）最后合并為 1 堆。因此，

13、在合并前作如下處理：/假設(shè)石頭每堆個數(shù)放于 stone1stonen,且 stonen之后最多 k-1 個數(shù)組單元為可寫：4-15 實現(xiàn)：若 a+b=n，則|a-b|越小，a*b 越大。貪心策略：因為因子互不相同，因此將 n 分成從 2 開始的連續(xù)自然數(shù)之和，若最后剩下一個數(shù)，將此數(shù)后項優(yōu)先的方式下均勻地分給前面各項。while (n % (k - 1) != 1)n+;stonen=0;最后再補充第三版算法實現(xiàn)題的 3-2 和 4-11，這兩題在第四版書中被刪除了，這兩題就是“最少找零錢”。3-2 實現(xiàn)（此題是第三版書的 3-2）：對比此題和 4-11 不同，4-11 的硬幣面值是確定的 5

14、,10,20,50,100 和 200，可以用貪心算法解決。而此題！這里注意各個硬幣的面值是輸入的，于 T1:n中。n 種面值，找錢數(shù) m。 cij：表示當使用面值 T1, , Ti這 i 種面值的硬幣時，需要找回錢數(shù) j 所使用的最少硬幣個數(shù)，這里 1in,1jm。若找不出找錢方案， cij 。cij的遞推表達式如下：cij mink ci 1 j k *Ti ，這里 k 表示最后一種幣值 Ti的0k j / T i。初始條件：ci0 0, i 1 nc1j ( j mod T1) 0 j / T1( j mod T1) 0或者這樣考慮也可以：設(shè) cj（j=1m）表示用所有錢幣 T1.n的找

15、錢 j 的最少錢幣。對于任何 1in,1jm，若 j-Ti0，則 cj-Ti表示找錢 j-Ti的最優(yōu)，再加上 1 張面值為 Ti的幣值就可以找回錢數(shù) j 了，且所用的錢為 cj-Ti+1。由此可知，cj min1 c j Tii 1 n, j 1 m1in c1 T1 11T1 14-11 實現(xiàn)（此題是第三版書的 4-11，此題貪心的簡單，但“貪心選擇性質(zhì)”的證明較為復雜，僅看看，不要求掌握證明?。簩Ρ却祟}和 3-2 不同，此題的硬幣面值是確定的 5,10,20,50,100 和 200，可以用貪心算法解決。而 3-2 題需用動態(tài)規(guī)劃來解決。找零的每步都選擇最大面值的硬幣，最終可以保證硬幣總

16、個數(shù)最少。【因為有較多同學對找零問題的貪心算法正確性證明有疑問，因此現(xiàn)證明如下：】對特定面值的找零錢問題的貪心算法正確性證明，先來看以 1 分，5 分，1 角，2 角五分這 4 種幣值的零錢最少面再寫）：找零，而此題的 5,10,20,50,100 和 200 分也同理可證（后設(shè)面值存于 c1=1,c2=5,c3=10,c4=25，找錢后各種面值為 s1:4，使得：4min i14s.t. sici n, 且si為非負整數(shù)i1（1）最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè) si,i=14 是上述找零問題的一個最優(yōu)解，則對任意 1j4 且 sj0，取 ti=si, 1i4,ij；tj=sj-1。則 ti, 1i4 是如

17、下子問題的最優(yōu)解。4min i14s.t. sici n c ji1（2）貪心選擇性質(zhì)此題貪心策略為優(yōu)先選擇盡可能的面值找零。則需證明對于任意一個值 n（n 為整數(shù)，以分為 ），都可以找到最佳找零方案包含小于 n 且最大的那種面值。假設(shè)，c1=1,c2=5,c3=10,c4=25，對于找零問題的任意一組最優(yōu)解 si, 1i4，一定有：s14，s21，s32，s4可能任意。【反證】：事實上，若 s15，則可以用 1張 c2面值的去替換 5 張 c1面值的錢；若 s22，則可以用 1 張 c3面值的去替換 2 張 c2面值的錢；若 s33，則可以用 1 張 c4面值和 1 張 c2面值的去替換 3

18、 張 c3面值的錢。這些替換都導致 si ,1i4 不是最優(yōu)解。另外，當 s3=2 時，一定有 s2=0，因如若不然，s21，由 2*c3+c2=c4可知，si ,1i4 不是最優(yōu)解。因此，現(xiàn)在對找零總數(shù) n（以分為，n 是整數(shù)）的各種情況：41）n25，由所有零錢總錢數(shù)為 n（即 sici n ），可知 s40。因如若不然，i133 sici n ，由前面分析可知，s1最大為 4，s2最大為 0，s3最大為 2， sici =i1i14*1+0*5+2*10，最大可能湊出 24，與 n25擇最大幣值的貪心策略；，假設(shè)不成立，因此 s40，滿足優(yōu)先選2）10n25，同理3）5n10，同理4）1n0，滿足貪心策略；，s20，滿足貪心策略；，s10，滿足貪心策略；此題的 5 分,10 分,20 分,50 分,100 分和 200 分面值設(shè)置：n%5 = = 0 才可找，若 n%50不可找。c1=5,c2=10,c3=20,c4=50,c5=100,c6=200。最優(yōu)子結(jié)構(gòu)顯然滿足。與前面的分析和證明同理，最優(yōu)解 s1:6，一定有 s11, s21, s32（若 s33，用 1 張 10 分的和 1 張 50 分的替換將產(chǎn)生更少的錢的）, s41, s51, s6可能任意。且當 s3=2 時，s2一定為 0