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

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

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

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

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

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

6、“先盡可能把第二艘船裝滿（最接近 c2），剩下看看能否裝上第一艘船？”（2）n 個(gè)箱子，能否盡可能多的將箱子裝上兩艘船？（指所有裝上船的箱子的數(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 個(gè)箱子。而這個(gè)問(wèn)題的最優(yōu)解，有多種方法可以裝到 8 個(gè)箱子，比如，10+10+10+15+20=65 裝入第一艘船，15+15

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

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

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

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

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

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

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

14、,10,20,50,100 和 200，可以用貪心算法解決。而此題！這里注意各個(gè)硬幣的面值是輸入的，于 T1:n中。n 種面值，找錢數(shù) m。 cij：表示當(dāng)使用面值 T1, , Ti這 i 種面值的硬幣時(shí)，需要找回錢數(shù) j 所使用的最少硬幣個(gè)數(shù)，這里 1in,1jm。若找不出找錢方案， cij 。cij的遞推表達(dá)式如下：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 的最少錢幣。對(duì)于任何 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 實(shí)現(xiàn)（此題是第三版書(shū)的 4-11，此題貪心的簡(jiǎn)單，但“貪心選擇性質(zhì)”的證明較為復(fù)雜，僅看看，不要求掌握證明?。簩?duì)比此題和 3-2 不同，此題的硬幣面值是確定的 5,10,20,50,100 和 200，可以用貪心算法解決。而 3-2 題需用動(dòng)態(tài)規(guī)劃來(lái)解決。找零的每步都選擇最大面值的硬幣，最終可以保證硬幣總

16、個(gè)數(shù)最少?！疽?yàn)橛休^多同學(xué)對(duì)找零問(wèn)題的貪心算法正確性證明有疑問(wèn)，因此現(xiàn)證明如下：】對(duì)特定面值的找零錢問(wèn)題的貪心算法正確性證明，先來(lái)看以 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為非負(fù)整數(shù)i1（1）最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè) si,i=14 是上述找零問(wèn)題的一個(gè)最優(yōu)解，則對(duì)任意 1j4 且 sj0，取 ti=si, 1i4,ij；tj=sj-1。則 ti, 1i4 是如

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

18、 張 c3面值的錢。這些替換都導(dǎo)致 si ,1i4 不是最優(yōu)解。另外，當(dāng) s3=2 時(shí)，一定有 s2=0，因如若不然，s21，由 2*c3+c2=c4可知，si ,1i4 不是最優(yōu)解。因此，現(xiàn)在對(duì)找零總數(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可能任意。且當(dāng) s3=2 時(shí)，s2一定為 0