計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第7章

PAGE41第7章 貪心算法假設(shè)數(shù)組A[1..n]和B[1..m]已經(jīng)排好序，A[1]￡A[2]￡…￡A[n]，和B[1]￡B[2]￡…￡B[m]。請?jiān)O(shè)計(jì)一個復(fù)雜度為O(n+m)的貪心算法在數(shù)組A[1..n]和B[1..m]中各找一個數(shù)A[u]和B[v]使得它們的差別|A[u]-B[v]|最小。解：我們先考慮A[1]和B[1]，記下他們的差|A[1]-B[1]|。當(dāng)然這個差很可能不是最小的。我們要繼續(xù)找更好的解。下一步該如何做呢？我們觀察到，如果A[1]B[1]，那么A[1]不可能在更好的解中，這是因?yàn)閷θ魏蜝[v]，v>1，都有|A[1]-B[v]||A[1]-B[1]|。類似地，如果A[1]>B[1]，那么B[1]不可能在更好的解中。這個過程很象合并二個序列，每次取兩序列的首項(xiàng)做比較，用它們的差來更新目前最佳解，然后，刪去較小的首項(xiàng)。根據(jù)這個觀察，我們有以下算法。Minimum-difference(A[1..n],B[1..m],u,v,d) //d=|A[u]-B[v]|是最小差值d?￥ //初始化i?1j?1whilei￡nandj￡m if|A[i]-B[j]|<d then u?i v?j d?|A[i]-B[j]| endif ifA[i]￡B[j] then i?i+1 else j?j+1 endifendwhilereturn(u,v,d)End因?yàn)樵诘?行到第14行的循環(huán)中，每檢查一對數(shù)字，A[i]和B[j]，我們就從兩序列中刪去一個數(shù)，所以，與合并算法類似，上述算法的復(fù)雜度為O(m+n)。請?jiān)O(shè)計(jì)一個復(fù)雜度為(nlgn)的算法來確定有n個數(shù)的集合A[1..n]中是否有兩個數(shù)字之和正好等于一個給定的數(shù)x。解：第一步，我們先將A[1..n]排序，使得A[1]≤A[2]≤A[3]≤…≤A[n]。 第二步，檢查A[1]+A[n]。如果A[1]+A[n]=x，則任務(wù)完成。否則，如果A[1]+A[n]<x，則A[1]不會在解中，下面的檢查可不考慮A[1]；如果A[1]+A[n]>x，則A[n]不會在解中，下面的檢查可不考慮A[n]。第三步，重復(fù)第二步的做法，在剩下的要檢查的序列中把首尾兩項(xiàng)相加。如果和為x則搜索成功，否則，在丟棄一個數(shù)字后的序列中繼續(xù)用這個辦法搜索直到找到答案。算法的偽碼如下。Search-SUM(A[1..n],x)SortA[1..n]suchthatA[1]≤A[2]≤A[3]≤…≤A[n]i1jnwhilei<j ifA[i]+A[j]=x thenreturn(true,i,j) else ifA[i]+A[j]<x thenii+1 elsejj-1 endif endifendwhilereturn(false)End因?yàn)榕判蛐枰?nlgn)時間，第4行到第12行的while循環(huán)需要O(n)時間，所以上面算法的復(fù)雜度為(nlgn)。給定一數(shù)組A[1..n]，請?jiān)O(shè)計(jì)一個O(nlgn)的算法來確定數(shù)組A中是否有兩個數(shù)A[i]和A[j](1i，jn)，使得A[i]=A[j]+1。如果有，則報(bào)告(i,j)，否則報(bào)告(0,0)。注意，數(shù)組A中的數(shù)可以是實(shí)數(shù)，不一定是整數(shù)。另外，i<j或i>j都可以。解：顯然，如果我們檢查所有可能的兩個數(shù)的話，我們就需要(n2)次運(yùn)算。我們的做法是，先把數(shù)組A[1..n]排序后放入另一數(shù)組B，使得B[1]≤B[2]≤B[3]≤…≤B[n]。我們把排序后的A[1..n]放入另一數(shù)組B，而不是數(shù)組A本身，是為了方便報(bào)告數(shù)字在原始序列中的序號。然后，用貪心法搜索是否有u和v使得B[u]=B[v]+1。如果有，找出它們在序列A中序號。設(shè)B[u]=A[i]，B[v]=A[j]，那么我們有A[i]=A[j]+1。在搜索u和v時，初始化指針v=1，u=2。如果B[u]=B[v]+1，則找到答案，輸出結(jié)果。否則，如果B[u]>B[v]+1，那么B[v]不可能在解中，故在下面搜索中可刪去，我們把指針v加1。如果B[u]<B[v]+1，那么B[u]不可能是解中的B[u]或A[i]，我們把指針u加1。這樣，最多經(jīng)過2n-1次比較就可有答案。下面是偽碼。Search(A[1..n],i,j) //n2B[1..n]A[1..n]SortB[1..n]suchthatB[1]≤B[2]≤B[3]≤…≤B[n]v1u2foundfalsewhileunandfound=false ifB[u]=B[v]+1 then foundtrue else ifB[u]>B[v]+1 //B[v]不可能是解的一部分 then vv+1 ifu=v //兩個數(shù)必須不同 thenuu+1 endif else uu+1 endif endifendwhileiffound=true then findisuchthatA[i]=B[u] //在數(shù)組B排序時就可留下對應(yīng)關(guān)系 findjsuchthatA[j]=B[v] return(i,j) else return(0,0)endifEnd因?yàn)榕判蚴巧厦嫠惴ǖ闹饕糠?，所以它的?fù)雜度是O(nlgn)。Toyota(豐田)公司在過去的n個月中生產(chǎn)的汽車數(shù)分別是A[1],A[2],…,A[n]。我們希望知道是否其中有一段時間，該公司生產(chǎn)的汽車總數(shù)正好等于M。也就是說，能否找到i和j(1￡i￡j￡n)，使得k=ijAk=M。請?jiān)O(shè)計(jì)一個O(n)的貪心算法找出i和解：顯然我們可假定A[k]0(1￡k￡n)。思路是，我們先從A[1]起把每月的產(chǎn)量累加。如果加到某個A[k]時，正好等于M，則得到解；如果小于M則繼續(xù)加下一個月的產(chǎn)量；如果超過M，說明A[1]不可能在解之中，把它從當(dāng)前累加和中丟棄，然后再繼續(xù)上述做法直到找到答案。Car-Production(A[1..n],M,i,j)j?i?1u?A[1] //初始累加數(shù)whilej￡n ifu=M then return(i,j) //找到答案 elseif u<M //到j(luò)為止的任何期間不可能有解 then j?j+1 u?u+A[j] //繼續(xù)累加 else i?i+1 //A[i]開始的任何區(qū)間不可能有解 u?u-A[i] //把A[i]從累加和中丟棄 endif //這時，如果i>j，則表明u=0 endifendwhilereturn(nosolution)end假設(shè)一長途汽車線路上有n個站點(diǎn)并順序編號為1，2，…，n，其中起點(diǎn)站為1，終點(diǎn)站為n。旅客可以從任一個站i上車(1≤i≤n-1)，到下面任一站j下車(i<j≤n)。假設(shè)已知p(i,j)為需要在站i上車，在站j下車的旅客人數(shù)(1￡i<j￡n)。又假設(shè)每部公共汽車?？棵恳粋€站并可載客30人。請?jiān)O(shè)計(jì)一個O(n2)算法來確定至少需要多少部汽車可以滿足所有旅客需要。解：我們先確定最擁擠的一段(i,i+1)至少需要多少不同的座位。然后用30去除即可。Minimum-Number-of-Buses(P,n)M?0 //初始化forj?2ton M?M+p(1,j) //從起點(diǎn)站出發(fā)總?cè)藬?shù)endforlargest?M //當(dāng)前找到的最擁擠的一段需要的座位數(shù)fori?2ton //計(jì)算從站i到i+1需要的座位數(shù) fork?1toi-1 //當(dāng)前的M是從站i-1到i需要的座位數(shù) M?M-p(k,i) //減去所有在站i下車人數(shù) endfor forj?i+1ton M?M+p(i,j) //加上所有在站i上車人數(shù) endfor ifM>largest thenlargest?M //更新最大值 endifendforreturnélargest/30ùEnd(a)請為下面表中的8個字符構(gòu)造哈夫曼編碼。它們在每100個字中出現(xiàn)的頻率在表中給出。字符頻率字符頻率A5.0E13.5B7.0F10.5C19.0G25.0D6.0H14.0在這個哈夫曼編碼中，平均每個字符需要多少比特？解:(a)構(gòu)造的前綴碼樹如下，每個字符的編碼顯示在每個字符下面。01H,14.0A01H,14.0A,5.01001B,7.0F,10.51043.50G,25.01024.501131.5D,6.0056.5110011.017.51010010111E,13.50001C,19.00000110101(3×13.5+4×6+4×5+219+2×25+3×14+4×10.5+4×7)/100=2.845。假設(shè)我們有n張照片和n個相框。為方便起見，假定它們的寬度都一樣但長度不等。這n張照片的長度由數(shù)組P[1..n]給出，而這n個相框的長度由數(shù)組F[1..n]給出。如果P[i]￡F[j](1i,jn)，那么第i張照片可以裝在第j個相框里。請?jiān)O(shè)計(jì)一個O(nlgn)的算法將盡可能多的照片配上相框并證明算法的正確性。注意，一張照片只許配一個相框，一個相框也只許配一張照片。解：把P[1..n]和F[1..n]排序，使得P[1]≤P[2]≤P[3]≤…≤P[n]，F(xiàn)[1]≤F[2]≤F[3]≤…≤F[n]。假設(shè)P[i]和F[j]分別是當(dāng)前照片序列和相框序列的頭，如果P[i]F[j]，我們則把它們配上，并記為(i,j)。否則F[j]不可能配仼何照片，丟棄之。然后再用同樣的方法為剩下的序列繼續(xù)配。偽碼如下。正確性證明隨后。Match-Photo-to-Frame(P[1..n],F[1..n])SortP[1..n]suchthatP[1]≤P[2]≤P[3]≤…≤P[n]SortF[1..n]suchthatF[1]≤F[2]≤F[3]≤…≤F[n]S?? //配好對的集合，初始為空i?j?1whilei￡nandj￡n ifP[i]￡F[j] then S?Sè(i,j) i?i+1 j?j+1 else j?j+1 endifendwhilereturnSEnd正確性證明：如果算法輸出的集合S為空，則說明P[1]>F[n]，顯然正確。所以我們只需考慮S非空的情況，這時，必有某個j使S含有對子(1,j)。并且，由算法知，F(xiàn)[j]是可以配P[1]中最短的，所有從F[1]到F[j-1]的相框都比P[1]短，從而不可能配任何相片。因此，我們只要能證明有個最佳解也包含對子(1,j)，那么算法就被證明正確了。這是因?yàn)?，配?1,j)后，最佳算法也不可能為F[1]到F[j-1]的相框配上任何相片。那么，最佳算法面對的剩余相片和相框的序列和我們面對的是完全一樣的。所以，算法重復(fù)同樣的方法，也必然是正確的。我們先證明存在一個最優(yōu)解，它含有對子(1,v)(這里的v也許不等于j)。我們用反證法。如果不是，而某個最佳解S*中照片長度最小的對子是(u,v)，u>1。那么，因?yàn)镻[1]￡P(guān)[u]，我們可用對子(1,v)換走(u,v)，集合M=(S*-{(u,v)}){(1,v)}仍是一個最優(yōu)解。這個最優(yōu)解含有對子(1,v)。我們再證明存在一個最優(yōu)解，它含有對子(1,j)。如果上面最優(yōu)解所含對子(1,v)等于(1,j)，則證明完成。如果不是，一定有v>j，這是因?yàn)樗惴ㄒ阉阉鬟^所有短于F[j]的相框，它們都不夠長。我們分兩種情況討論。最優(yōu)解M中沒使用F[j]。對這種情況，我們只需用對子(1,j)換走(1,v)即可。最優(yōu)解M使用了F[j]，有對子(w,j)。那么，我們有關(guān)系P[1]￡P(guān)[w]￡F[j]￡F[v]。所以，我們可以重新配對，用對子(1,j)和(w,v)換走(1,v)和(w,j)。這樣得到的集合仍是最優(yōu)解而且含有對子(1,j)。算法的主要部分是排序，所以有復(fù)雜度O(nlgn)。用貪心法設(shè)計(jì)一個O(n)的算法解決第2章習(xí)題3的問題。為方便起見，問題重述如下。假設(shè)Google公司在過去n天中的股票價格記錄在數(shù)組A[1..n]中。我們希望從中找出兩天的價格，其價格的增幅最大。也就是說，我們希望找到A[i]和A[j](i<j)使得M=A[j]–A[i]的值最大，即M=max{A[j]–A[i]|1￡i<j￡n}。解：思路是，我們先找到小規(guī)模的解，然后逐步擴(kuò)大。具體做法是，先找到兩個數(shù)A[1..2]的最優(yōu)解，再找出A[1..3]的最優(yōu)解，等等，直到找出A[1..n]的最優(yōu)解。假設(shè)我們已找出A[1..i]的最優(yōu)解，如何找A[1..i+1]的最優(yōu)解呢？因?yàn)槲覀円延蠥[1..i]的最優(yōu)解，我們只需考慮是否A[i+1]可以帶來更好的解。A[i+1]可以帶來的最好解是A[i+1]減去A[1..i]中最小的值，即d=A[i+1]–min{A[k]|1ki}。我們只要把d和A[1..i]的最優(yōu)解比較一下就可以了。根據(jù)這個思路，在算A[1..i]的最佳解時，我們一方面要更新目前最好的解，另一方面還要更新目前為止A[1..i]中最小的數(shù)以便下一步使用。偽碼如下。Max-Profit(A[1..n],m,i,j) //假定n>1，m是要找的最大差價。m?-￥ //初始值。min-index?1 //目前看到的數(shù)組A中最小的數(shù)的序號。fork2ton ifA[k]–A[min-index]>m //A[k]帶來更優(yōu)解，要更新。 then m?A[k]–A[min-index] i?min-index j?k endif ifA[k]<A[min-index] //無論有無更好解，總要更新最小的數(shù)。 thenmin-index?k endifendforreturn(m,i,j)End顯然，這是個O(n)算法。有n個活動a1，a2，…,an需要使用同一個禮堂。禮堂從時刻t=0可以使用，但是任何時刻只能安排最多一個活動。這些活動沒有定死的開始或終止時刻，但都希望從t=0開始。假設(shè)第i個活動(1in)需要連續(xù)使用ti時間。如果在時刻t>0開始，那么必須要付出額外的開銷。這個開銷與開始時刻t成正比。為簡單起見，就把開始時刻t作為開銷。請?jiān)O(shè)計(jì)一算法來找到一個最佳調(diào)度使總的開銷最小。也就是說，如果活動ai開始時刻是si，算法要找到一個兩兩兼容的調(diào)度使i=1nsi最少。請證明算法正確性和分析解：我們的做法是先把活動以ti(1in)為關(guān)鍵字從小到大排好。然后以這個順序從t=0開始逐個安排。下面是偽碼，證明隨后。Minimum-Overhead-Scheduling(T[1..n],S[1..n]) //計(jì)算最佳的開始時間S[1..n]SortT[1..n]suchthatT[1]T[2]…T[n] //把活動以ti排序。S[1]?0 //從t=0開始安排。fori?2ton S[i]S[i-1]+T[i-1]endforEnd算法復(fù)雜度因排序而有O(nlgn)。正確性證明:顯然，在任一個最佳調(diào)度中，兩個相鄰的活動不會有時間間隔，而第一個安排的活動必定從t=0開始。下面我們證明存在一個最優(yōu)調(diào)度，它安排的活動的順序與上面算法得到的一致。我們用反證法證明。假如不存在這樣的最優(yōu)調(diào)度，那么在一個最優(yōu)調(diào)度中，一定存在兩個相鄰的活動ai和aj使得T[i]>T[j]但ai卻安排在aj之前。這樣相鄰的一對活動稱為一個顛倒。我們假定最優(yōu)調(diào)度M是所有最優(yōu)調(diào)度中顛倒數(shù)最少的。如果它的顛倒數(shù)為0，則算法得證。故假定M有兩個相鄰的活動ai和aj使得T[i]>T[j]但ai卻安排在aj之前。下面圖(a)顯示了這種情況?，F(xiàn)在，如下圖(b)所示，如果我們交換ai和aj的順序可得到一個新的調(diào)度S*。它們的交換不影響其他活動的安排，但卻使ai和aj的開銷從S[i]+S[j]變?yōu)镾*[i]+S*[j]。因?yàn)镾[i]=S*[j]而S[j]=S*[i]–T[j]+T[i]>S*[i]。所以新的調(diào)度有較小開銷。這與M是最優(yōu)調(diào)度矛盾。所以，最優(yōu)調(diào)度不可以含有顛倒。因此，算法是正確的。 某劇場舉辦一個電影節(jié)。劇場內(nèi)有二個電影院，X和Y。在從t=0開始的某一段時間內(nèi)，電影院X會順序放映n個長短不一的電影x1，x2，…，xn，其每場開始和結(jié)束時間順序?yàn)?a1，b1)，(a2，b2)，…，(an，bn)。從t=0開始，在同一期間，電影院Y會連續(xù)放映m個電影，y1，y2，…，ym，其每場開始和結(jié)束時間順序?yàn)?c1，d1)，(c2，d2)，…，(cm，dm)。我們規(guī)定每位觀眾必須準(zhǔn)時入場并不得中途退場。假定兩電影院之間距離極近，覌眾從一個影院走到另一個所需時間為零。請?jiān)O(shè)計(jì)一個時間為O(m+n)的貪心算法以決定同一個觀眾最多可以看完幾場電影，并為他選出這些電影。你必須解釋為什么你的算法可給出最佳的解，即保證看到最多的電影。解：解的思路是，從t=0開始，決定下一場電影是去電影院X還是Y去看。如果b1￡d1那么去電影院X看x1。這個決定不會錯，因?yàn)槿绻罴呀獠缓衳1，那么最佳解中第一個看的電影要么是y1，或者是b1以后影院X放映的電影。如果是y1，則將y1換為x1后仍是一個最佳解。如果第一個看的電影是b1以后影院X放映的電影，則可把x1加入到最佳解中而看到更多的電影。因此，如果b1￡d1選取x1不會錯。反之，如果b1>d1則選y1。一旦選中，那么下一個要做決定的時刻就是看完第一場電影那個時刻(b1或d1)。這時可用同樣的原理來決定下一場電影是去電影院X還是去Y。在作決定前，要找到各影院下一場開映的時間。下面是該算法的偽碼。Movie-Selection(X[1..n],Y[1..m],S) //S是選中電影的集合S?current-time?0 //當(dāng)前選下部電影的時刻i?1 //電影院X的下一個要考慮的電影j?1 //電影院y的下一個要考慮的電影whilei￡nandj￡m ifbi￡dj then S?Sè{xi} i?i+1 current-time?bi whilecj<current-timeandj<m j?j+1 //電影yj必須在current-time之后開映。 endwhile else S?Sè{yj} j?j+1 current-time?dj whileai<current-timeandi<n i?i+1 //電影xi必須在current-time之后開映。 endwhile endifendwhileifi>n //電影院X的所有電影已檢查完畢。thenfork?jtom //電影院Y的剩余電影都可以看。 S?Sè{yj} endfor elsefork?iton S?Sè{xi} endforendifEnd這個算法顯然有O(m+n)復(fù)雜度，因?yàn)槊總€電影只檢查一次便決定取舍，而每次檢查只需O(1)時間?？紤]一個加權(quán)的完全圖G(V,E)，其中頂點(diǎn)集合是V={v1,v2,…,vn}。每個頂點(diǎn)vi(1￡i￡n)含有一個整數(shù)ai。邊(vi,vj)的權(quán)值是|ai–aj|。下面一個圖給出了一個5個頂點(diǎn)的例子。我們希望找到一條經(jīng)過每個點(diǎn)正好一次的路徑(哈密爾頓路徑)使得路徑的總的權(quán)值最小。這里，一條路徑的權(quán)值是路徑上所有邊的權(quán)值總和。頂點(diǎn)內(nèi)的數(shù)字不計(jì)入權(quán)值。(其實(shí)，把頂點(diǎn)內(nèi)數(shù)字計(jì)入權(quán)值不會改變解。)(a)請?jiān)O(shè)計(jì)一個貪心算法來找到這條最佳路徑。你可以選擇任一點(diǎn)開始和仼一點(diǎn)結(jié)束。(b)重復(fù)(a)，但是你必須從點(diǎn)vi開始和到vj結(jié)束(ij)。解：(a) 我們先把頂點(diǎn)按所含整數(shù)的大小排序使得a1￡a2￡…￡an。那么這條路徑可從a1的頂點(diǎn)開始，按照這個排序順序走到含an的頂點(diǎn)止。下面給出偽碼，證明隨后。TSPP(A[1..n])SortverticessuchthatA[1]￡A[2]￡…￡A[n]returnthepathof<v1,v2,…,vn> //vi含整數(shù)ai(1≤i≤n)。End正確性證明：我們用歸納法證明，對任一個序號k(1kn)，存在一個最優(yōu)解，b1，b2，…，bn，使得b1是最小的，b2是第2小的，…，bk是第k小的。歸納基礎(chǔ)：當(dāng)k=1時，設(shè)最優(yōu)解為b1，b2，…，bn。因?yàn)榘研蛄蟹聪蚝笕匀皇且粋€最優(yōu)解，不失一般性，可假定b1bn。如果b1不是最小的，那么，因?yàn)樾蛄兄杏斜萣1小的數(shù)而b1bn，所以一定可以找到兩個相鄰的數(shù)，bi和bi+1，使得bi<b1￡bi+1。因此，如果我們把b1插入其中，則會得到一個更好的序列。我們來觀察一下。變化前的序列：b1，b2，…，bi，bi+1，…，bn變化后的序列：b2，b3，…，bi，b1，bi+1，…，bn因?yàn)?b1–bi)+(bi+1–b1)=bi+1–bi，變化后的序列的總權(quán)值比變化前的少了|(b2–b1)|。所以，如果第一個數(shù)不是最小的，我們總可以作上述變換，直到第一個數(shù)是最小的數(shù)為止。所以可假定b1是最小的。歸納基礎(chǔ)得證。從上面討論我們還觀察到，如果有一個頂點(diǎn)序列或子序列是按照它們所含數(shù)字大小排列的話，則不論序列有多長，其對應(yīng)路徑的總權(quán)值就等于最大數(shù)減去最小數(shù)。歸納步驟：假設(shè)最佳解的前k個頂點(diǎn)所含的整數(shù)是最小的k個數(shù)并且有b1￡b2￡…￡bk。我們證明bk+1是余下序列中最小的。假設(shè)bk+1不是最小的而bj，j>k+1，是最小的。那么，如果我們把bj抽出來并插到bk+1前面，我們會得到一個更優(yōu)序列。讓我們來比較一下。我們分二種情況討論：j=n。變化前的序列：b1，b2，…，bk，bk+1，…，bn-1，bn變化后的序列：b1，b2，…，bk，bn，bk+1，…，bn-1因?yàn)閎kbn<bk+1，變化后的序列的總權(quán)值比原序列減少bn-1–bn0。j<n。變化前的序列：b1，b2，…，bk，bk+1，…，bj-1，bj，bj+1，…，bn變化后的序列：b1，b2，…，bk，bj，bk+1，…，bj-1，bj+1，…，bn這種情況下，變化后的序列的總權(quán)值比原序列減少:(bj-1-bj)+(bj+1–bj)–|bj+1–bj-1|=min(bj-1,bj+1)–bj+max(bj-1,bj+1)–bj–[max(bj-1,bj+1)–min(bj-1,bj+1)]=2[min(bj-1,bj+1)–bj]0。 所以，存在一個最佳解，它的前k+1個頂點(diǎn)所含的整數(shù)是最小的k+1個數(shù)并且有b1￡b2￡…￡bk￡bk+1，歸納成功。我們先把頂點(diǎn)按所含整數(shù)的大小排序使a1￡a2￡…￡an?？紤]任何一條從點(diǎn)vi開始到vj結(jié)束的最優(yōu)路徑。在這個路徑上，有兩種情況：v1排在vn前面。我們可以把這條最優(yōu)路徑分三段。第1段是從ai所在頂點(diǎn)到a1所在頂點(diǎn)v1，用[ai..a1]表示；第2段是從a1所在頂點(diǎn)v1到an所在頂點(diǎn)vn間的這一段路徑，用[a1..an]表示；第3段是從an所在頂點(diǎn)vn到aj所在頂點(diǎn)vj，用[an..aj]表示。根據(jù)前面討論，第2段序列[a1..an]對應(yīng)的整數(shù)必定是排好序的。另外，第1段[ai..a1]中點(diǎn)的整數(shù)值必須在a1和ai之間，否則不會最優(yōu)。這是因?yàn)槿绻袛?shù)字x>ai，我們可以將x抽出后插入到第2段序列[a1..an]中而減少總權(quán)值。同理，第3段[an..aj]中點(diǎn)的整數(shù)值必須在an和aj之間。這也就是說最優(yōu)序列對應(yīng)的整數(shù)序列可分三段，而且，每段中數(shù)字是排好序的。所以，這個最優(yōu)路徑的總權(quán)值必為(ai-a1)+(an-a1)+(an–aj)=(ai–aj)+2(an-a1)。進(jìn)一步，我們還可以看到，如果在第1段[ai..a1]中有點(diǎn)x，x≠ai，x≠a1，我們都可以把x抽出后插入第2段序列[a1..an]中而總權(quán)值不變。所以可認(rèn)為最優(yōu)解中的第1段只有一個點(diǎn)ai。同理可認(rèn)為最優(yōu)解中的第3段只有一個點(diǎn)aj。v1排在vn后面。類似對(1)的討論，這個最優(yōu)序列對應(yīng)的整數(shù)序列可分三段：ai，[an..a1]，aj，其中，第2段含有除ai和aj外的所有點(diǎn)并排好序。所以，這個最優(yōu)路徑的總權(quán)值為(an–ai)+(an-a1)+(aj–a1)=(aj–ai)+2(an-a1) 由上面討論可知，如果i<j，最佳序列對應(yīng)第一種情況，它由下面三段組成：ai，[a1..an]，aj，總權(quán)值為(ai–aj)+2(an-a1)。如果i>j，最佳序列對應(yīng)第二種情況，它由下面三段組成：ai，[an..a1]，aj，總權(quán)值為(aj–ai)+2(an-a1)。根據(jù)以上討論，算法如下。Path(A[1..n],i,j)Sortverticessuchthata1￡a2￡…￡anDeleteaiandajfromthesequence //把a(bǔ)i和aj從序列中刪去Lettheremainingsequencebe[a1..an]ifai<aj thenreturnai，[a1..an]，aj elsereturnai，[an..a1]，aj endifEnd假設(shè)我們有n個活動，a1，a2，…,an，要租用學(xué)校的教室。每個活動ai(1￡i￡n)有一個固定的開始時間si和一個固定的完成時間fi(0si<fi<)。安排在同一教室的活動必須兩兩兼容。假設(shè)學(xué)校有足夠的教室可以從t=0開始使用。請?jiān)O(shè)計(jì)一個O(nlgn)貪心算法找到一個調(diào)度使我們能租用最少的教室以滿足所有n個活動要求。這里，一個調(diào)度是指，租用多少教室，以及每個教室安排哪幾個兩兩兼容的活動。(這個問題也被稱為區(qū)間圖著色問題。假如把每對si和fi(1￡i￡n)看作實(shí)數(shù)軸上區(qū)間[si，fi)的話，我們可以構(gòu)造一個有n個頂點(diǎn)的區(qū)間圖。其中n個頂點(diǎn)對應(yīng)這n個區(qū)間(也代表了這n個活動)。如果兩個頂點(diǎn)代表的區(qū)間有重疊部分，則它們之間有一條邊。對一個圖著色就是給圖中每個點(diǎn)一個顏色使得相鄰兩點(diǎn)的顏色不同。顯然，同一種顏色的點(diǎn)所代表的區(qū)間兩兩不重疊。這也就是說，它們對應(yīng)的活動兩兩兼容，可以安排在同一教室。所以，用最少的顏色給區(qū)間圖著色就對應(yīng)了用最少的教室安排這n個活動。)解：設(shè)這n個活動對應(yīng)的開始和結(jié)束時間分別放在數(shù)組S[1..n]和F[1..n]中。一個簡單但不正確的做法是，先用書上7.2節(jié)的算法Greedy-Activity-Selection(s[1..n],f[1..n])找到一組最大的兩兩兼容的活動，并分配一個教室給它們。然后，再用這辦法在余下的活動中找一組最大的兩兩兼容的活動，并分配第2個教室給這組活動。繼續(xù)這樣做直到n個活動全部安排好。這個算法在最壞情況下要O(n2)時間并且不保證最優(yōu)。試看下面一例。i1234si1264fi3578如果用這個簡單方法，我們須租用3個教室：H-1={a1，a3}，H-2={a2}，H-3={a4}。但是最好的結(jié)果是H-1={a1，a4}，H2={a2，a3}。那么，應(yīng)該怎祥做才正確呢？一個正確的做法是：把2n個開始和結(jié)束時刻在一起排序。假設(shè)這個序列是C。C[1]為最小時刻。顯然是某個活動的開始時刻。用h記錄當(dāng)前一共開啟了多少教室。需要開啟一個新教室時，h加1，并且標(biāo)記新教室為H-h。已開啟過的教室中，當(dāng)前閑置可用的教室標(biāo)號都存在數(shù)組A[1..j]中。開始時，可用教室的集合為空(j=0)。從C[1]開始，逐個檢查C[k]，1￡k￡2n。如果C[k]是某活動ai的開始時刻，C[k]=S[i]，那么:(3.1)如果j>0，則分配給ai標(biāo)號為A[j]的教室，然后j減1。(3.2)如果j=0，則沒有現(xiàn)成可用的教室，需開啟一個新教室，把標(biāo)號放入A[1]中，j加1。然后，把這個新教室A[1]分配給活動ai后，j減1(又等于0了)。如果C[k]是某個活動ai的結(jié)束時刻，C[k]=F[i]，則把它占有的教室釋放。做法是，j加1后，該教室的標(biāo)號放回A[j]中。下面是偽碼，正確性證明隨后。Classroom(S[1..n],F[1..n],L[1..n],h)//L[i]是活動ai被分配的教室號碼。教室號碼從1開始按照被啟用順序標(biāo)號，//h是當(dāng)前被啟用的教室個數(shù)。C[1..2n]Sort{S[i],F[i]|1￡i￡n} //把2n個開始和結(jié)束時刻在一起排序。//如果有F[i]=S[j]，把F[i]放在S[j]前面。即先釋放ai所用教室，后給aj分配教室//如果有F[i]=F[j]或S[i]=S[j]，順序可任意。j?h?0 //可用教室的集合是A[1..j]，一開始為空fork1to2n ifC[k]=S[i]forsomei //如果C[k]是活動ai的開始時刻 then ifj=0 //如果可用教室的集合為空 then h?h+1 j?1 A[j]H-h //開啟新教室，標(biāo)號放入A[j] endif L[i]?A[j] //分配教室A[j]給ai j?j-1 else ifC[k]=F[i]forsomei //C[k]是活動ai的結(jié)束時刻 then j?j+1 A[j]L[i] //L[i]是ai使用的教室號 endif endifendforEnd正確性證明：上面算法是正確的，證明如下：顯然，算法檢查每一個開始時間si并為每一個活動ai都分配一個教室，并且到完成時刻fi之前不會釋放，所以，所有活動都被滿足。另外，分配在任一個教室的活動是兩兩兼客的。這是因?yàn)槊看伍_啟一個教室時，用的是新標(biāo)號。所以每個教室的標(biāo)號是唯一的。當(dāng)標(biāo)號為A[j]的教室分配給某活動ai后，一直到活動ai釋放前，該標(biāo)號就不存在于數(shù)組A中。因此，標(biāo)號為A[j]的教室不可能同時被兩個活動使用。另外，一個活動一結(jié)束，它占用的教室馬上退回到數(shù)組A。所以，一個教室要么正在使用，要么回到數(shù)組A。算法所用的教室數(shù)h最小。這是因?yàn)椋?dāng)我們?yōu)槟郴顒觓i而需要開啟最后一個，即第h個教室時，j=0，表明所有已啟用的其他教室目前都被占用。由（1）知，不同的教室被不同的活動占用。這表明在時刻S[i]，有h-1個活動正在同時進(jìn)行，而且沒有活動在S[i]結(jié)束。（既使有某個F[j]=S[i]，因?yàn)镕[j]排序在S[i]前面，aj已被處理。）現(xiàn)在，又來了新活動ai，所以有h個活動在時刻S[i]之后的一段時間里需要同時進(jìn)行，少于h個教室不可能滿足要求。所以算法所用的教室數(shù)最少。上面算法中的排序需要O(nlgn)時間，而后的循環(huán)需要O(n)時間，所以有復(fù)雜度O(nlgn)。在第6章習(xí)題6中，我們考慮過焊接n個鋼管的問題。這里，我們再次考慮這個焊接問題。不同的是，我們不限制焊接時鋼管之間的順序。每一次焊接，你可以任選兩根鋼管來焊接。現(xiàn)在，我們把問題再描述一下。假設(shè)我們需要把n個鋼管，a1,a2,…,an，焊成一根鋼管。這些鋼管的重量分別是W[i](1￡i￡n)。每次焊接你可以從被焊鋼管中任選二根來焊，但每次焊接的代價等于被焊兩根鋼管重量之和。比如我們有5根鋼管，重量為3，8，5，10，13。顯然，任何一個焊接計(jì)劃可以用一個有n個葉子的完全二義樹表示。如果我們按下面二叉樹所示的順序焊接，那么總的代價為(5+8)+(13+13)+(3+10)+(26+13)=91.(a) 假設(shè)有一棵n個葉子的完全二叉樹T表示一個焊接計(jì)劃，證明這個焊接計(jì)劃的總代價為Cost(T)=k=1nWkdepth(k)，其中depth(k)是代表鋼管(b)如果一個焊接計(jì)劃有最小的總代價，則稱為最佳焊接計(jì)劃。證明在一個對應(yīng)最佳焊接計(jì)劃的二叉樹T中，代表最輕二根鋼管的葉子在最底層。(c)證明有一個最佳焊接計(jì)劃，它的第一步是把最輕的二根鋼管焊在一起。(d)設(shè)計(jì)一個O(nlgn)的算法為這n個鋼管產(chǎn)生一個最佳焊接計(jì)劃。解：因?yàn)殇摴躠k的重量W[k]在每次含有這根鋼管的焊接中被記入代價一次，而含有這根鋼管的焊接次數(shù)正好等于depth(k)。所以，由鋼管ak導(dǎo)致的代價是W[k]depth(k)。例如，在上面的二叉樹中，重量為8的鋼管出現(xiàn)在3次焊接中，它導(dǎo)致的代價就是83=24。那么，把所有鋼管導(dǎo)致的代價加在一起即得到公式Cost(T)=k=1nWkdepth(k)。(亦可用歸納法證明。)例如，在上面的二叉樹中，總代價就是132+53+83+32+10(b)不失一般性，假設(shè)W[1]和W[2]是最輕二根鋼管的重量，W[1]W[2]。假設(shè)W[1]的葉子不在最底層。那么因?yàn)門是個完全二叉樹，在最底層一定有個葉子代表W[k]，而W[k]>W[2]?，F(xiàn)在，如果我們讓W(xué)[1]的葉子代表W[k]，而讓W(xué)[k]的葉子代表W[1]，那么作這樣交換后的焊接計(jì)劃的代價是：Cost(new)=Cost(T)–W[1]depth(1)–W[k]depth(k)+W[1]depth(k)+W[k]depth(1)=Cost(T)–(W[1]–W[k])depth(1)+(W[1]-W[k])depth(k)=Cost(T)–(W[1]–W[k])[depth(1)-depth(k)]這里的depth(1)和depth(k)都是交換前的深度。因?yàn)閃[1]<W[k]和depth(1)<depth(k)，所以有Cost(new)<Cost(T)，與T代表最佳焊接計(jì)劃矛盾。所以代表W[1]的葉子在最底層。同理可證代表W[2]的葉子也在底層。(c) 因?yàn)橛幸粋€代表最佳焊接計(jì)劃的二叉樹T，其中代表最輕的二根鋼管的葉子在最底層。不失一般性，設(shè)W[1]和W[2]為它們的重量。因?yàn)榇硭鼈兊娜~子都在最底層，如果和W[1]的葉子共一個父親的葉子不是W[2]而是W[k]的話，我們可以讓代表W[2]的葉子代表W[k]而讓代表W[k]的葉子代表W[2]。這樣一來，W[1]和W[2]的葉子有同一個父結(jié)點(diǎn)。而且，因?yàn)檫@個交換是在同一層進(jìn)行，總代價不變?，F(xiàn)在，按照新的計(jì)劃，最輕的二根鋼管可以在第一步焊在一起。(d)從上面幾個問題的答案可知，找一個最佳焊接計(jì)劃和找一個哈夫曼編碼的過程完全一樣。故有下面的偽碼。Least-Cost-Welding(W[1..n],c) //c是總代價ifn=1 thenreturn(c=0)endifConstructamin-heapHonW[1..n] //為W[1..n]構(gòu)造最小堆，每個數(shù)對應(yīng)一個結(jié)點(diǎn)fori?1ton-1 x?extract-min(H) //提取堆中最小數(shù) y?extract-min(H) //提取堆中第2小數(shù) constructanodezwithtwochildren//構(gòu)造有二個兒子的結(jié)點(diǎn)z left(z)?x //以x為根(或葉子)的子樹是z的左子樹 right(z)?y //以y為根(或葉子)的子樹是z的右子樹 W(z)?W[x]+W[y] //x和y的重量和為z的重量insert(H,z) //將z插入堆中endforreturnH[1] //以H[1]為根的二叉樹代表一個最佳焊接計(jì)劃End算法的正確性由以上討論已清楚。因?yàn)槊看卧谧钚《焉系牟僮餍枰狾(lgn)時間，算法復(fù)雜度為O(nlgn)。作為例子，下面圖中的二叉樹是題目中例子的最佳焊接計(jì)劃。考慮一個與上題不同的焊接問題。假設(shè)我們需要把n個鋼管，a1,a2,…,an，焊成一根鋼管。這些鋼管的直徑不同，分別是D[i](1￡i￡n)。假設(shè)焊接點(diǎn)的強(qiáng)度與被焊兩根鋼管直徑的乘積成正比。為簡單起見，就假定這焊點(diǎn)強(qiáng)度等于被焊兩根鋼管直徑的乘積。顯然，焊接完成后的鋼管有(n-1)個焊點(diǎn)，而它的強(qiáng)度就等于這(n-1)個焊點(diǎn)中最薄弱的焊點(diǎn)強(qiáng)度。我們注意到，把鋼管排成不同的順序來焊會得到不同的強(qiáng)度。比如，4根鋼管的直徑分別是2，4，5，8。如果按這個順序焊的話，三個焊點(diǎn)強(qiáng)度分別是24，45，和58。所以，焊好后的鋼管強(qiáng)度是8。但如果焊接順序是2，8，5，4，那么焊好后的鋼管強(qiáng)度是min{28，85，54}=16。請?jiān)O(shè)計(jì)一個O(nlgn)的貪心算法來確定一個最優(yōu)的焊接順序使焊好后的鋼管強(qiáng)度最大。你需要證明算法的正確性。解：直覚告訴我們，焊接時應(yīng)粗細(xì)鋼管搭配著焊。如果二根粗的相鄰，就一定會有二根細(xì)的相鄰而造成薄弱的焊點(diǎn)。所以如果把直徑D[i](1￡i￡n)排序的話，那么焊接順序應(yīng)該是A[1]，A[n]，A[2]，A[n-1]，A[3]，A[n-2]，…。我們將證明這個直覺是對的。下面是偽碼。正確性證明隨后。Largest-Strength-Welding(D[1..n],B[1..n]) //數(shù)組B給出最佳焊接順序。SortD[1..n]suchthatD[1]≤D[2]≤…≤D[n]k=n/2fori=1tok B[2i-1]i //鋼管序號放入數(shù)組B B[2i](n–i+1) endforifn>2k //n是奇數(shù) then B[n]k+1 //D的中位數(shù)endifEnd正確性證明：首先，我們證明存在一個最優(yōu)序列，其中A[1]在序列的頭部或尾部。如果不是，那么A[1]在最優(yōu)序列的中間?？杉俣ㄗ顑?yōu)序列是A[i],…,A[j],A[1],A[k],…?，F(xiàn)在，如果我們把從A[i]到A[1]這段子序列，即A[i],…,A[j],A[1]，翻轉(zhuǎn)一下的話，得到下面的新序列：A[1],A[j],…,A[i],A[k],…。因?yàn)镈[1]D[i]，D[i]D[k]D[1]D[k]，按這個新序列焊接的鋼管只會有更大的強(qiáng)度，不會削弱。所以我們可確定A[1]在最優(yōu)序列的頭部。下一步，我們證明在一個最優(yōu)序列中，A[n]是在序列中的第二個鋼管。假設(shè)最優(yōu)序列是A[1],A[i],…,A[n],A[q],…，而A[i]A[n]，D[i]≤D[n]。那么，如果我們把從A[i]到A[n]這一段子序列翻轉(zhuǎn)的話，我們會得到一個新的序列：A[1],A[n],…,A[i],A[q],….。因?yàn)镈[1]D[n]D[1]D[i]，D[q]D[i]≥D[1]D[i]，這個新序列引入的兩個新焊點(diǎn)的強(qiáng)度都不比原序列中第一個焊點(diǎn)弱。所以這個新序列也是最優(yōu)的。這就證明了存在一個最優(yōu)序列以A[1]，A[n]開頭。我們觀察到，因?yàn)閷θ魏蝘>1，D[1]D[n]D[i]D[n]，所以無論那一根鋼管排在A[n]后面，它和A[n]之間的焊點(diǎn)不會影響整個鋼管的強(qiáng)度。所以，我們只要保證余下的(n-2)根鋼管有最大強(qiáng)度即可。重復(fù)上面的推理，我們可知，在某個(n-2)根鋼管的最優(yōu)序列中，開頭兩鋼管是A[2]，A[n-1]。這也就是說，原問題的一個最佳序列中A[1]，A[n]，A[2]，A[n-1]是開頭的4項(xiàng)。顯然，我們可以繼續(xù)這樣做下去，所以算法產(chǎn)生最優(yōu)的焊接順序。算法的主要時間化在排序，所以有O(nlgn)復(fù)雜度。假設(shè)我們開一部卡車從城市A到城市B，沿路經(jīng)過一些蘋果市場。城市A和城市B也有蘋果市場。為方便起見，假定一共有n個市場，順序編號為1到n，其中城市A的市場為第1號，城市B的市場為第n號。在每個市場i(1≤i≤n)，我們可以買蘋果，買入價格已知為B[i](元/斤)，也可以賣蘋果，賣出價為S[i]。我們希望在某個市場i買蘋果，然后在某市場j賣掉，ji，使得賺的錢最多，即M=S[j]-B[i]最大。請?jiān)O(shè)計(jì)一個O(n)的貪心算法找出這兩個市場i和j并報(bào)告這個最大差價M=S[j]-B[i]。我們規(guī)定，車子只能向前開，不可以往回開。你可以在同一市場買和賣，但只能買一次和賣一次。如果這個最大差價是負(fù)數(shù)也給予報(bào)告，說明最少會虧多少。解：和第8題的思路一樣，我們先找到小規(guī)模的解，然后逐步擴(kuò)大。具體做法是，先考慮k=1的情況，即只能在市場1買和賣，然后考慮k=2的情況，即可以在市場1和2買和賣，隨后再考慮k=3的情況，等等，直到找出k=n時的最優(yōu)解。假設(shè)我們已找出k=i時的最優(yōu)解，如何找k=i+1的最優(yōu)解呢？我們只須考慮是否市場i+1可以帶來更好的解。市場i+1可以提供的最好解是，在市場1到市場i+1中以最低價買入，以S[i+1]賣出，即d=S[i+1]–min{B[k]|1ki+1}。我們只要把d和k=i時的最優(yōu)解比較一下就可以了。根據(jù)這個思路，在算k=i時的最佳解時，我們一方面要更新目前最好的解，另一方面還要更新目前為止{B[k]|1ki}中最小的數(shù)以便下一步使用。偽碼如下。Max-Apple-Profit(B[1..n],S[1..n],M,i,j) MS[1]–B[1]ij1lowest1foru2ton ifB[u]<B[lowest] thenlowestu //更新最低買入價 endif ifS[u]–B[lowest]>M then MS[u]–B[lowest] //更新最好結(jié)果 ilowest ju endifendforreturn(M,i,j)上面算法顯然有O(n)復(fù)雜度。*重新考慮上面第15題。假設(shè)我們做兩次買賣，即在某個市場i1買蘋果，然后在某市場j1i1賣掉，這是第一次買賣。然后，我們再在某市場i2j1買蘋果和在市場j2i2賣掉。我們希望兩次買賣的總收入最大，即M=(S[j1]-B[i1])+(S[j2]-B[i2])最大。我們規(guī)定，車子只能向前開，不可以往回開。你可以在同一市場買和賣，但只能最多買兩次和賣兩次。如果這個最大差價是負(fù)數(shù)也給予報(bào)告。請?jiān)O(shè)計(jì)一個O(n)貪心算法解決這個問題。解：這個問題的關(guān)鍵是找出兩次買賣的最佳分界點(diǎn)k，也就是說我們要決定市場k，使得第一次買賣在市場1到市場k之間進(jìn)行，而第二次買賣在市場k到市場n之間進(jìn)行的總結(jié)果最好。這似乎是動態(tài)規(guī)劃問題，但不需用動態(tài)規(guī)劃。讓我們定義以下符號。L[k]表示在市場1到市場k之間進(jìn)行一次買賣可得最大收益，R[k]表示在市場k到市場n之間進(jìn)行一次買賣可得最大收益。那么，原問題的解是M=max1≤k≤n我們用類似上一題的貪心法，在O(n)時間內(nèi)，算出所有L[k](1≤i≤n)。同樣，在O(n)時間內(nèi)，算出所有R[k](1≤i≤n)。那么M可在O(n)時間內(nèi)得到。偽碼如下。Max-Apple-Profit-Two-trade{B[1..n],S[1..n],M} L[0]-ij1lowest1fork1ton ifB[k]<B[lowest] thenlowestk //更新有最低買入價格的市場 endif ifS[k]–B[lowest]>L[k-1] then L[k]S[k]–B[lowest] L-Buy[k]lowest //市場1到k之間最佳買入點(diǎn) L-Sell[k]k //市場1到k之間最佳賣出點(diǎn) else L[k]L[k-1] L-Buy[k]L-Buy[k-1] L-Sell[k]L-Sell[k-1] endifendforR[n+1]- //從右向左算R[k]，初始化ijnhighestn //S[n]是當(dāng)前最高賣出價forkndownto1 ifS[k]>S[highest] thenhighestk //更新最高賣出價市場 endif ifS[highest]–B[k]>R[k+1] then R[k]S[highest]–B[k] R-Buy[k]k //市場k到n之間最佳買入點(diǎn) R-Sell[k]highest //市場k到n之間最佳賣出點(diǎn) else R[k]R[k+1] R-Buy[k]R-Buy[k+1] R-Sell[k]R-Sell[k+1] endifendforM-fork1ton ifL[k]+R[k]>M then ML[k]+R[k] divide-pointk endifendforreturnM,L-Buy[divide-point],L-Sell[divide-point],R-Buy[divide-point],R-Sell[divide-point]End這個算法顯然有O(n)復(fù)雜度。這個算法有動態(tài)規(guī)劃的影子，但劃入貪心法更合適，因?yàn)樵谟?jì)算L[k]和R[k]時，每一步只用到一個確定的子問題的解，不存在動態(tài)選擇問題?？紤]一個與第6章習(xí)題10有關(guān)的問題。如下圖所示，兩條平行線A和B上各有n個點(diǎn)，并且從左到右依次編號為1，2，3，…，n。另外，直線A上每個點(diǎn)和直線B上唯一的一個點(diǎn)有線段相連，反之亦然。設(shè)直線A上點(diǎn)i與直線B上點(diǎn)π(i)相連，那么這n個線段為(i,π(i))(1≤i≤n)。下圖的例子中，我們有π(1)=3,π(2)=1,π(3)=6,π(4)=8,π(5)=2,π(6)=5,π(7)=4,π(8)=7。如果i<j但是π(i)>π(j)，那么線段(i,π(i))和(j,π(j))會相交，否則不相交。第6章習(xí)題10要求找出最大的一組互不相交的線段。本題的問題是要把這些線段分組使得在同一組里的線段互不相交。例如，在下圖中，這8個線段可分為三組：{(1,3),(3,6),(4,8)}，{(2,1),(5,2),(6,5),(8,7)}，{(7,4)}。請?jiān)O(shè)計(jì)一個O(n2)的貪行算法用最少的組數(shù)把這n個線段分組使得在同一組里的線段互不相交。(可改進(jìn)為O(nlgn))解： 我們用貪心法順序處理這n個線段。一開始，我們把(1,π(1))放入第一組。當(dāng)我們處理(i,π(i))時，就順序查看每一組，一旦找到一組，其線段都與(i,π(i))兼容(互不相交)，則把(i,π(i))放入該組。如果已建立的每一組中都有線段與(i,π(i))相交(不兼容)，那我們就新增加一組，把(i,π(i))放入該組，并順序給這一組編號。注意，當(dāng)我們檢查某一組是否與(i,π(i))兼容時，我們只需要檢查該組中最后一個放入的線段是否與(i,π(i))兼容即可，也就是有最大序號j或最大π(j)值的線段(j,π(j))。偽碼如下，證明隨后。Min-Number-of-Groups([1..n],k,S[1..k]) //輸出k個組，S[1]到S[k]k1 //第一組組號S[1]{(1,[1])} //起始只有一個組S[1]，含線段(1,[1])maxpi[1]π(1) //maxpi[j]=max{π(p)|(p,π(p))S[j]}fori2ton //順序檢查每個線段 foundfalse //為(i,[i])找一可加入的集合 j1 while(found=false)andjk if[i]>maxpi[j] then found=true S[j]S[j]{(i,[i])} maxpi[j][i] else jj+1 endif endwhile iffound=false then kk+1 //只好為(i,[i])新建一個集合 S[k]{(i,[i])} maxpi[k][i] endifendforreturnk,S[1..k]End正確性證明：我們可假定，每個分組中的線段按序號順序排列。我們對算法中的循環(huán)變量i用歸納法證明以下命題：存在一個最佳解，它對線段(1,[1]),(2,[2]),…,(i,[i])的分組與上面算法Min-Number-of-Groups的分組一樣。歸納基礎(chǔ)：當(dāng)i=1時，只有一個線段。我們可以把最佳解中有線段(1,[1])的集合標(biāo)為S[1]。命題顯然正確。歸納步驟：假設(shè)存在一個最佳解M，它對線段(1,[1]),(2,[2]),…,(i-1,[i-1]),2in,的分組與上面算法的分組一樣，分為k組。我們證明存在一個最佳解M*，它對線段(1,[1]),(2,[2]),…,(i-1,[i-1]),(i,[i])的分組與上面算法的分組一樣。我們分3種情況分析：線段(i,[i])不能放入已有的k組中任何一組，因?yàn)槊恳唤M都有線段與(i,[i])相交([i]<maxpi[j]，j=1,2,…,k)。這種情況下，最佳解M也必須為(i,[i])新建一個集合。我們可以把該集合標(biāo)為S[k+1]。命題得證。存在一個或幾個集合與線段(i,[i])兼容。這種情況下，上面的算法找到最小的j，使(i,[i])與S[j]兼容，把(i,[i])放入S[j]。如果最佳解M也把(i,[i])放入S[j]，那么，最佳解M就是M*，它對線段(1,[1]),(2,[2]),…,(i-1,[i-1]),(i,[i])的分組與上面算法的分組一樣。命題得證。如果最佳解M不把(i,[i])放入S[j]，而是放入S[u]中，u>j。那么，在剛要放(i,[i])時，必有maxpi[j]>maxpi[u]。原因如下：設(shè)maxpi[j]=[j’]，maxpi[u]=[u’]，(j’,[j’])和(u’,[u’])分別是S[j]和S[u]中最后一個線段。如果u’>j’，那么必有[u’]<[j’]，否則兩線段兼容，根據(jù)算法，當(dāng)我們處理(u’,[u’])時，應(yīng)該把(u’,[u’])放入S[j]中或更前面的集合。如果u’<j’，那么也必有[u’]<[j’]，否則當(dāng)我們處理(u’,[u’])時，(u’,[u’])必與S[j]中所有線段都不相交，應(yīng)該放入S[j]中或更前面的集合。因此，必有maxpi[j]>maxpi[u]。讓我們記M[j,i]=maxpi[j]，M[u,i]=maxpi[u]，表示這兩個數(shù)是在我們處理(i,[i])時的值，并有M[j,i]>M[u,i]。因?yàn)樽罴呀釳在(i,[i])之后放入集合S[j]中的任何線段(w,[w])，w>i，都必須有[w]>M[j,i]>M[u,i]。所以，在(i,[i])之后，最佳解M放入集合S[j]中的任何線段都與(i,[i])之前放入集合S[u]中的任何線段不相交。同時，最佳解M在(i,[i])之后放入集合S[u]中的任何線段(w,[w])，w>i，都必須有[w]>[i]>M[j,i]。所以，在(i,[i])之后放入集合S[u]中的任何線段(包括(i,[i]))都與(i,[i])之前放入集合S[j]中的任何線段不相交。我們可以把最佳解M中集合S[u]和集合S[j]中(i,[i])之后的線段(包括(i,[i]))進(jìn)行交換。顯然，交換后的集合S[j]和S[u]中的線段仍然不相交，并且集合的個數(shù)不變。因此，交換后得到的解M*也是最佳解，并且線段(i,[i])被放到S[j]中，命題得證。存在一個或幾個集合與線段(i,[i])兼容（當(dāng)然包括S[j]）但是最佳解M不把(i,[i])放入S[j]，而是放入新建的一個集合S[v]中，v>k。這種情況與(B)相似，我們可以把S[v]和集合S[j]中(i,[i])之后的線段(包括(i,[i]))進(jìn)行交換得到解M*。歸納成功。所以，上面算法輸出的分組數(shù)是最少的，算法的復(fù)雜度顯然是O(n2)。注意，由上面證明中對情況(B)的討論知，算法運(yùn)行的任何時刻都有maxpi[1]>maxpi[2]>…>maxpi[k]。所以用二元搜索可把算法復(fù)雜度改進(jìn)為O(nlgn)。假設(shè)A[1]，A[2]，…，A[n]是n個數(shù)的一個序列，請?jiān)O(shè)計(jì)一個O(n2)貪心算法把它分成最少的幾個遞增的子序列。這里，遞增意味不減少，即遞增序列中允許相等數(shù)字。例如，序列4，8，2，3，6，9，7可以分為兩個子序列：<4，8，9>，<2，3，6，7>。顯然這是最好的了。(可改進(jìn)為O(nlgn))解：這題與上一題有相同本質(zhì)，因?yàn)檫f增序列中的兩個數(shù)字，A[i]和A[j]，如果i<j，那么必有A[i]A[j]。把A[i]視為[i]就變?yōu)樯弦活}了。 偽碼如下。Min-Number-of-Increasing-Subsequences(A[1..n],k,S[1..k]) //輸出k個序列，S[1]到S[k]k1S[1,1]A[1] //起始只有一個序列S[1]，含A[1])last[1]1 //S[1]中有1個數(shù)fori2ton foundfalse //為A[i]找一個序列接上 j1 while(found=false)andjk ulast[j] //S[j]的最后一個數(shù) ifA[i]S[j,u] then found=true S[j,u+1]A[i] //A[i]接在S[j]后面 last[j]u+1 //更新S[j]中數(shù)字個數(shù) else jj+1 endif endwhile iffound=false then kk+1 //只好為A[i]新建一個序列 S[k,1]A[i] last[k]i endifendforreturnk,S[1..k]End*重新考慮第3章習(xí)題13中構(gòu)造最小優(yōu)先樹的問題。給定一個n個數(shù)的序列，A[1]，A[2]，…，A[n]，用貪心法設(shè)計(jì)一個最壞情況O(n)的算法為這個序列構(gòu)造出最小優(yōu)先樹。解：貪心法的思路是，先構(gòu)造只有一個數(shù)的最小優(yōu)先樹，然后構(gòu)造二個數(shù)的最小優(yōu)先樹，再構(gòu)造三個數(shù)的最小優(yōu)先樹，等等。也就是說，每次在前面已構(gòu)造好的最小優(yōu)先樹中插入一個新的數(shù)使其成為一個新的最小優(yōu)先樹。關(guān)鍵是，如何能快速地插入。假設(shè)我們已構(gòu)造了序列A[1]，A[2]，…，A[i-1]的最小優(yōu)先樹?，F(xiàn)在考慮如何插入A[i]。顯然，如果我們對A[1]，A[2]，…，A[i-1]的最小優(yōu)先樹做中序遍歷的話，內(nèi)結(jié)點(diǎn)的順序一定是A[1]，A[2]，…，A[i-1]。下面圖(a)顯示的是插入A[i]前的這個最小優(yōu)先樹，其中A[i-1]是最后一個內(nèi)結(jié)點(diǎn)。它的右子樹一定是個葉子，而左子樹不一定。 如果我們順著從A[i-1]到根這條路徑走的話，數(shù)字會一個比一個小。當(dāng)我們碰到一個結(jié)點(diǎn)的數(shù)a滿足aA[i]時停下。假定結(jié)點(diǎn)a的右兒子是數(shù)字b，那么我們有aA[i]<b。這說明a小于等于序列中他右邊的任何數(shù)，包括A[i]。所以，原來最小優(yōu)先樹中a左邊的結(jié)構(gòu)不需改變。但是，因?yàn)锳[i]<b，所以，a的右兒子應(yīng)該是A[i]而不是b。所以，我們第一步要做的是把a(bǔ)的右兒子改為A[i]。因?yàn)锳[i]是序列中到A[i]為止的最后一個數(shù)，所以A[i]的右兒子是個葉子。而A[i]的左兒子應(yīng)該是從結(jié)點(diǎn)a之后到A[i-1]為止這一段的最小優(yōu)先樹。這恰恰就是原先以b為根的子樹。所以，插入A[i]的步驟如下：順著從A[i-1]到根的路徑找到第一個結(jié)點(diǎn)A[k]滿足A[k]A[i]切下A[k]的右兒子R置A[k]的右兒子為A[i]置A[i]的左兒子為R置A[i]的右兒子為一片樹葉。下面是偽碼。復(fù)雜度分析隨后。不難看出，當(dāng)A[i]比根里的數(shù)字還小或比A[i-1]還大時，下面算法仍正確。Min-First-Tree(A[1..n],T)root?A[1]left(root)?nilright(root)?nil //先為A[1]建二叉樹，nil表示葉子，沒有數(shù)字(root)?nil //A[1]的父親為空fori?2ton //從A[2]開始，逐個插入這個二叉樹 a?A[i-1] whilea>A[i]andanil a?[a] endwhile ifa=nil //A[i]比根里的數(shù)還小 then left(A[i])?root //原來的樹成了A[i]左兒子 (root)?A[i] right(A[i])?nil root?A[i] //A[i]是新的根 (root)?nil else b?right(a) left(A[i])?b (b)?A[i] right(A[i])?nil right(a)A[i] (A[i])?a endifendforEnd現(xiàn)在來分析一下復(fù)雜度。當(dāng)我們在插入A[i]時，我們沿著A[i-1]到根的路徑走。如果我們經(jīng)過了k次比較而在結(jié)點(diǎn)a處停下的話，那么在a之前比較過的k個數(shù)字都隨著a的右子樹被切去而永遠(yuǎn)不會再出現(xiàn)在將來被檢查的路徑上。假定在我們插入A[i]時作了n(i)次比較，那么總的比較次數(shù)是i=2nn(i)。因?yàn)槲覀冊诓迦階[i]時要從這條被檢查路徑上永久除去n(i)–1個數(shù)，所以我們一共除去的數(shù)字有i=2n(ni=2n(ni-1)=i=2nn(i)-(n-1)n-1，也就是i=2nn(i)所以，總的比較次數(shù)是i=2nn(i)2(n-1)。由此，算法的復(fù)雜度是O(n設(shè)計(jì)一個復(fù)雜度為O(n)的算法來解第2章習(xí)題20。問題敘述如下。在序列A[1]，A[2]，…，A[n]中，如果一個數(shù)出現(xiàn)的次數(shù)k超過一半，即k>n/2，那么這個數(shù)稱為壟斷數(shù)(dominatingnumber)。如果序列有壟斷數(shù)，則報(bào)告這個數(shù)及其出現(xiàn)次數(shù)k，否則報(bào)告k=0。規(guī)定，算法只能用比較序列中兩數(shù)字是否相同來判斷，比較不告訴誰大誰小，只告訴相同或不相同。其它數(shù)字間的比較無此限制。解：我們的策略是，把不同的數(shù)字配對，任何兩個不同的數(shù)字都可以配。我們用集合S來保存當(dāng)前還沒有配上對子的數(shù)，起始為空。顯然，集合S中的數(shù)有相同的數(shù)值。從A[1]開始，我們逐個掃描序列，A[1]，A[2]，…，A[i]，…。如果A[i]與集合S中的數(shù)不相等，則取集合S里一個數(shù)與A[i]配對。否則，則把A[i]放入集合S。一個有趣的觀察是，如果序列有一個壟斷數(shù)x，它一定出現(xiàn)在集合S中。這是因?yàn)闆]有足夠的數(shù)可以與它配對。所以，如果有壟斷數(shù)，唯一可能的數(shù)就是在集合S中的那個數(shù)x。我們只要再數(shù)一下序列中有多少個數(shù)等于x即可得解。管理集合S最方便的數(shù)據(jù)結(jié)構(gòu)是堆棧。算法顯然有復(fù)雜度O(n)。下面是偽碼。Dominating-Number(A[1..n],u,k) //如果有，A[u]是壟斷數(shù)，出現(xiàn)k次，否則u=0,k=0S //堆棧初始為空 fori1ton ifS= then Push(S,A[i]) //壓A[i]進(jìn)棧 ui else ifA[i]=A[u] thenPush(S,A[i]) elsePop(S) //A[i]與Top(S)配對，不需記錄 endif endifendfor ifS then k0 fori1ton ifA[i]=A[u] then kk+1 endif endforendififk>n/2 thenreturnu,k elsereturn0,0endifEnd*改進(jìn)7.5節(jié)中最佳加油計(jì)劃問題的貪心算法使其復(fù)雜度為O(n)。解：7.5節(jié)中最佳加油站問題的貪心算法的復(fù)雜度取決于L。如果在L公里內(nèi)最多有k個加油站，那么這個復(fù)雜度為O(kn)。這是因?yàn)樵诿總€停靠站要檢查最多k個油站的價格和距離，處理時間為O(k)。所以總的時間為O(kn)。這個算法可改進(jìn)為，在k為任意變量時，復(fù)雜度仍為O(n)。關(guān)鍵的思路是，每個油站的價格和距離只檢查一次以省去重復(fù)計(jì)算的時間。假設(shè)我們?？吭诩佑驼緄。我們看一下算法對兩種情況的處理。在L公里內(nèi)，加油站k是第一個加油站滿足P[k]<P[i]。那么，我們在當(dāng)前加油站i加入正好能跑到加油站k的油。下一個停靠站是k。在L公里內(nèi)任一加油站價格都大于等于P[i]。這種情況下，找出最遠(yuǎn)的一個價格最低的加油站k。這時，應(yīng)把油箱加滿，并且下一站應(yīng)停在加油站k。如果