計算機算法基礎 第2版 習題及答案 第6章

PAGE44第6章 動態(tài)規(guī)劃假設矩陣A、B、C、D、E的維數(shù)序列如下，找出其最佳連乘順序。(a)5,10,3,12,5,50解：最佳順序為(((AB)(CD))E)。

8,10,6,11,3,35解：最佳順序為((A(B(CD)))E)。

找出下面二序列的最長公共子序列：<1,0,0,1,0,1,0,1>和<0,1,0,1,1,0,1,1,0>iiyj010110110j01234567890000000000001111111101122222220112223333012233344401233344450123444555012344555601234556660xi112030410xi1120304150617081它們的LCS是<1,0,0,1,1,0>，其長度為6。下面表中列出了搜索7個關鍵字A[1..7]的各種情況的概率。請為他們找出一個最佳二元搜索樹并求出其平均復雜度。i01234567pi0.040.060.080.020.100.120.14qi0.060.060.060.060.050.050.050.05解：表W(i,j),ji\0123456710.060.160.280.420.490.640.811.0020.060.180.320.390.540.710.9030.060.200.270.420.590.7840.060.130.280.450.6450.050.200.370.5660.050.220.4170.050.2480.05

表E(i,j),ji\0123456710.060.280.621.021.341.832.443.1220.060.300.680.931.411.962.6130.060.320.571.041.482.1340.060.240.571.011.5550.050.300.721.2060.050.320.7870.050.3480.05表root(i,j),ji\012345671-12223352-2333553-334554-45565-5666-677-7這個最佳二元搜索樹如下。它的平均復雜度是3.12次比較。AA[5]A[2]A[1]A[3]A[6]A[7]d0d1d2d3d4A[4]d6d5d7給出一個在序列A[1..n]中找最長遞增子序列的O(nlgn)算法的偽碼。解： Improved-LCS(A[1..n],L,B,length)L?L[1]?1 //當前只有一個長度l=1的初始解[1]?nil //父親未知S[0]?A[0]- //因二元搜索的需要，加的一個左邊點T[0]?0 //S[0]在序列A中的序號S[1]?A[1] //長度為1的子序列的結尾元素開始只有A[1]T[1]?1 //S[1]在序列A中的序號S[L+1]? //因二元搜索的需要，加的一個右邊點fori=2ton Binary-search(S,0,L+1,A[i],k) //調用二元搜索子程序，其偽碼在后面。 //找出k使得S[k]A[i]<S[k+1]，見下面?zhèn)未a。 L[i]?k+1 //L[i]長度必為k+1 [i]?T[k] //A[i]接在A[j]后面，這里[i]=j=T[k] S[k+1]?A[i] //因為A[i]<S[k+1],更新S[k+1] T[k+1]?i //同時更新對應的序號 ifL[i]>L then L?L+1 S[L+1]? //多了一個長度 endifendfor //下面找出最大的L[i]值index?1fori=2ton ifL[index]<L[i] thenindex?iendforlength?L[index] //下面把找到的LIS輸出到B[1..length]forj=lengthdownto1 B[j]?A[index] index?[index]endforreturnB[1..length]End BinarySearch(S,p,r,x,k) //輸入時有S[p]x<S[r]，輸出k使得S[k]x<S[k+1]ifp=r then kp exitendifmidpoint??(p+r)/2?ifS[midpoint]>x thenBinarySearch(S,p,midpoint,x,k) elseBinarySearch(S,midpoint,r,x,k)endifEnd假設我們要將一根大型長鋼管鋸成若干段。我們在要鋸的地方打上標記，一共是n個標記。這些標記距離鋼管左端的距離，從左到右，分別是a1，a2，…，an厘米。這個鋼管的總長是l厘米，l>an(參見下圖)。當我們將鋼管鋸為兩截時，需要的代價與當時被鋸鋼管的長度成正比，比例是每一厘米p元。請用動態(tài)規(guī)劃設計一個算法，找出最優(yōu)的順序來完成這n處的切割并使總的代價最小。分析你的算法的復雜度。(提示：用a0=0和an+1=l表示鋼管左端和右端位置。用[ai,aj]表示從標記ai到標記aj這段鋼管。用C(i,j)表示完成對[ai,aj]這段鋼管的切割任務所需的最小代價，也就是完成所有ak(i<k<j)處的切割所需代價。找出C(i,j)的歸納公式。)以下面數(shù)據(jù)為例，用你在(a)中的算法找出最優(yōu)的切割順序和總代價。請顯示你的計算過程。a1=2，a2=5，a3=9，a4=14，l=15，p=1。解：(a) 定義C(i,j)=切割鋼管[ai,aj]（子問題）所需最小代價。我們有以下歸納公式：C(i,j)=mini+1≤k≤j-1{C(i,k)+C(i,j)=0 (初始解) 如果j=i+1在下面的偽碼中，我們用表S[i,j]記錄切割鋼管[ai,aj]的位置。Optimal-Cutting(A,n,p)fori?0ton C[i,i+1]?0 //初始解endforforl?2ton+1 //l=j–i是子問題的規(guī)模 fori?0to(n+1)–l j?i+l C[i,j]?￥ fork?i+1toj-1 q?C[i,k]+C[k,j]+p(aj–ai) ifq<C[i,j] then C[i,j]?q S[i,j]?k endif endfor endforendforreturnCandSEnd上面算法的復雜度顯然是O(n3)。(b) a1=2,a2=5,a3=9,a4=14,l=15,p=1。表C、表S和表示順序的二叉樹構造如下，總的代價是35元。a1a1a2a3a4a3a2a4a1如下圖所示，順序放好的n根鋼管的重量順序為W[i](1￡i￡n)。我們需要把他們依照順序焊成一根鋼管，但每次焊接可任意選兩根相鄰的鋼管來焊接。每次焊接的代價與被焊兩段鋼管的總重量成正比。為簡單起見，把代價定為被焊兩段鋼管的總重量。例如，W[1]=5,W[2]=1,W[3]=2，如果先把W[1]和W[2]焊好，代價為5+1=6。焊好的這塊有重量6，再把W[3]焊上，又要代價6+2=8，總代價是14。但如果先焊W[2]和W[3]，再焊W[1]，則總代價為11。用動態(tài)規(guī)劃設計一個算法，計算出最優(yōu)的焊接順序使總代價最小。應用你上面的算法求出以下5根鋼管的最優(yōu)焊接順序和總代價：W[1]=8,W[2]=1,W[3]=7,W[4]=2,W[5]=9。解：(a) 我們用[ai,aj]表示把從ai到aj這一段的鋼管焊好后的鋼管。找[ai,aj]的最優(yōu)焊接順序定義為子問題。我們定義C(i,j)=將鋼管[ai,aj]焊好的最小代價(子問題的解，1ijn)。我們有以下歸納公式：C(i,j)=mini≤k≤j-1{Ci,k+CkC(i,i)=0 (初始解，i=1，2，…，n)如果定義W(i,j)=t=ijW[t]C(i,j)=mini≤k≤j-1{Ci,kC(i,i)=0 在下面的偽碼中，我們用表S[i,j]記錄將鋼管[ai,aj]分為兩段的地方，也就是最后一次應焊的位置。表W(i,j)(1￡i￡j￡n)可以先計算好。Welding(W,n)fori?1ton C[i,i]?0endfor //初始解forl?1ton-1 fori?1ton–l j?i+l C[i,j]?￥ fork?itoj-1 q?C[i,k]+C[k+1,j]+W(i,j) //W(i,j)已算好，偽碼在后面 ifq<C[i,j] then C[i,j]?q S[i,j]?k endif endfor endforendforreturnCandSEndWeight(W,n)fori?1ton W[i,i]?W[i]endforfori?1ton-1 forj?i+1ton W[i,j]?W[i,j-1]+W[j] endforendforreturnWEnd(b)W[1]=8,W[2]=1,W[3]=7,W[4]=2,W[5]=9。解:表W(i,j),j表C(i,j),j1234512345189161827109243662218101920818373791830927421140115950表S(i,j),j1234511113223433444最優(yōu)焊接順序由下面二叉樹表示?？偞鷥r為62(=8+16+11+27)。如下圖所示，順序放好的n根鋼管的重量順序為W[i](1￡i￡n)。我們需要把他們依照順序焊成一根鋼管，但每次焊接可任意選兩根相鄰的鋼管來焊接。每次焊接的代價與被焊兩段鋼管中的較重的一根的重量成正比。為簡單起見，就把代價定為被焊兩段鋼管中的較重的一根的重量。例如，W[1]=5,W[2]=1,W[3]=2，如果先把W[1]和W[2]焊好，代價為5，再把W[3]焊上，又要代價6，總代價是11。但如果先焊W[2]和W[3]，再焊W[1]，則總代價為2+5=7。用動態(tài)規(guī)劃設計一個算法，計算出最優(yōu)的焊接順序使總代價最小。應用你上面的算法求出以下5根鋼管的最優(yōu)焊接順序和總代價：W[1]=6,W[2]=2,W[3]=7,W[4]=5,W[5]=8。解：(a) 我們用[ai,aj]表示把從ai到aj這一段的鋼管焊好后的鋼管。找[ai,aj]的最優(yōu)焊接順序定義為子問題。定義C(i,j)=將鋼管[ai,aj]焊好的最小代價(子問題的解，1ijn)。我們有以下歸納公式：C(i,j)=mini≤k≤j-1{Ci,k+Ck+1,j+maxt=ikWt,t=k+1jWt} 如果j>i，C如果定義W(i,j)=t=ijWC(i,j)=mini≤k≤j-1{Ci,k+CkC(i,i)=0。 在下面的偽碼中，我們用表S[i,j]記錄將鋼管[ai,aj]分為兩段的地方，也就是最后一次應焊的位置。表W(i,j)(1￡i￡j￡n)可以先計算好。Welding(W,n)fori?1ton C[i,i]?0 //初始解endforforl?1ton-1 fori?1ton–l j?i+l C[i,j]?￥ fork?itoj-1 q?C[i,k]+C[k+1,j]+max{W(i,k),W(k+1,j)} ifq<C[i,j] then C[i,j]q S[i,j]?k endif endfor endforendforreturnCandSEndWeight(W,n)fori?1ton W[i,i]?W[i]endforfori?1ton-1 forj?i+1ton W[i,j]?W[i,j-1]+W[j] endforendforreturnWEnd(b)W[1]=6,W[2]=2,W[3]=7,W[4]=5,W[5]=8。解：表W(i,j),j表C(i,j),j1234512345168152028106142537229142220716283712203071945134085850表S(i,j),j1234511223223333444

最優(yōu)焊接順序由下面二叉樹表示?？偞鷥r為37(=6+8+8+15)。假設一通訊公司要設計一個n路的復用器。它把n條平行的輸入線路并入到一條輸出線路。這個復用的過程是逐步實現(xiàn)的。它每次把相鄰的兩條線路并為一條輸出線路。如果這兩條線路的帶寬分別是a和b的話，那么合并后的輸出線路有帶寬a+b。經(jīng)過一系列兩兩合并后，我們得到一條輸出線路，它的帶寬是所有輸入帶寬之和。下面的圖給出n=5的一個例子。我們假定在合并兩條帶寬分別是a和b的線路時的硬件代價為a+b。下圖例子中的設計需要的硬件總代價是25+27+37+64=153。MUXMUXMUXMUXMUXW1=10W2=15W3=12W4=18W5=9W=25W=37W=27W=64n-wayMUX假設這n條輸入線路的帶寬依次為W1，W2，…，Wn，用動態(tài)規(guī)劃設計一個算法來確定最優(yōu)的合并順序以使硬件總代價最小。應用你的算法為下列帶寬序列確定合并的最佳順序并給出硬件總代價：W[1]=13,W[2]=21,W[3]=17,W[4]=12,W[5]=25。解：(a)這道題和第6題做法一樣。定義C(i,j)=將Wi到Wj之間所有線路合并的最小代價(子問題的解，1ijn)。我們有以下歸納公式：C(i,j)=mini≤k≤j-1{Ci,k+CkC(i,i)=0 如果定義W(i,j)=t=ijW[t]C(i,j)=mini≤k≤j-1{Ci,kC(i,i)=0 在下面的偽碼中，我們用表S[i,j]記錄求C(i,j)時得的k值。表W(i,j)(1￡i￡j￡n)可以用下面子程序Bandwidth(W,n)先計算好。MUX(W,n)fori?1ton C[i,i]?0endforforl?1ton-1 fori?1ton–l j?i+l C[i,j]?￥ fork?itoj-1 q?C[i,k]+C[k+1,j]+W(i,j) ifq<C[i,j] then C[i,j]q S[i,j]?k endif endfor endforendforreturnCandSEndBandwidth(W,n)fori?1ton W[i,i]?W[i]endforfori?1ton-1 forj?i+1ton W[i,j]?W[i,j-1]+W[j] endforendforreturnWEnd(b)W[1]=13,W[2]=21,W[3]=17,W[4]=12,W[5]=25。表C(i,j),j表W(i,j),j123451234510348512620511334516388203879150221385075302983317295440374123750525表S(i,j),j12345112222223334445合并的順序如下?？偞鷥r為34+29+54+88=205。MUXMUXMUXMUXMUXW1=13W2=21W3=17W4=12W5=25W=34W=54W=29W=88假設我們有三個字母或數(shù)字的序列，X[1..m]=x1x2...xm，Y[1..n]=y1y2...yn，和Z[1..m+n]=z1z2...zm+n。如果序列Z是由X和Y中的元素按順序交匯而成，那么Z被稱為X和Y的一個洗牌。例如，下面圖中的序列Z=cchocohilaptes是X=chocolate和Y=chips的一個洗牌。 YY=chipsX=chocolateZ=cchocohilaptes用動態(tài)規(guī)劃設計一個算法來確定序列Z是否是X和Y的一個洗牌。(提示：用M[i,j]=1表示Z[1..i+j]是X[1..i]和Y[1..j]的一個洗牌。然后找出歸納公式。)用你的算法確定以下三序列中，Z是否是X和Y的一個洗牌。X=FEAST, Y=LOVE, Z=FLOEVASET解一：有個簡單的方法是先求X和Z的最長公共子序列W。如果WX，則Z不可能是X和Y的一個洗牌。如果W=X，檢查把X從Z中刪去后的序列是否等于Y。如果是，則Z是解二：(a) 我們建一個表M，其中M[i,j]=1(1im,1jn)表示Z[1..i+j]是X[1..i]和Y[1..j]的一個洗牌。我們有以下歸納公式。M[0,0]=1 (初始解，i=j=0)如果(j>0,M[i,j-1]=1和Z[i+j]=Y[j])或者(i>0,M[i-1,j]=1和Z[i+j]=X[i])，那么M[i,j]=1否則M[i,j]=0。如果M[m,n]=1，那么Z是X和Y的一個洗牌。偽碼如下。Shuffle(X[1..m],Y[1..n],Z[1..m+n]，M，D) //D[i,j]是指向子問題的指針M[0,0]1fori?0tom forj?0ton if(j>0andM[i,j-1]=1andZ[i+j]=Y[j]) then M[i,j]1 D[i,j]?“” else if(i>0andM[i-1,j]=1andZ[i+j]=X[i]) then M[i,j]1 D[i,j]?“” else M[i,j]0 D[i,j]?nil endif endif endforendforifM[m,n]=1 thenreturnyesandD elsereturnnoendifEnd算法顯然有復雜度O(mn)。算法中表D可省略，但如果要知道Z是如何洗牌得到的，那么可從D得到。(b)X=FEAST, Y=LOVE, Z=FLOEVASET。表MY[j]LOVEX[i]01234010000F111100E200110A300010S400011T500001由上表知Z是X和Y的一個洗牌。一塊長方形電路板的上下兩邊各有n個端口并用數(shù)字順序標為1，2，3，…，n。根據(jù)電路設計的要求，我們需要把上邊的n個端口和下邊的n個端口一一配對后用導線連接。假設與上邊第i個端口號連接的下邊的端口號是π(i)，那么要連接的n個對子為(i,π(i))(1≤i≤n)。下面的圖給出了一個n=8的例子。在這個例子中，我們有π(1)=3，π(2)=1，π(3)=6，π(4)=8，π(5)=2，π(6)=5，π(7)=4，π(8)=7。現(xiàn)在需要把這些對子分組使得在一組里的導線不相交從而可以分布在同一個絕緣層上。比如，在下圖中，連接對子(1,3),(3,6),(4,8)的導線是不相交的。如何用最少的組數(shù)把它們分開是個有趣的問題但不在此討論。現(xiàn)在的問題是，我們只找一組導線不相交的對子集合，使得它含有的對子最多。比如在下圖中，{(2,1),(5,2),(6,5),(8,7)}就是最大的一組導線不相交的對子集合，它含有4個導線不相交的對子。請用最長遞增子序列算法里的方法設計一個O(n2)算法來找出一組最大的導線不相交的對子集合。解：我們注意到，如果有一組導線不相交的對子，(i1,π(i1)),(i2,π(i2)),…,(ik,π(ik))，其中i1<i2<…<ik，因為他們的導線都不相交，那么我們必須有π(i1)<π(i2)<…<π(ik)。也就是說，這些電路板下方的端口號是一個遞增序列。反過來，如果在序列,π(1),π(2),…,π(n)中有一個遞增子序列，π(i1)<π(i2)<…<π(ik)，那么{(i1,π(i1)),(i2,π(i2)),…,(ik,π(ik))}就一定是一組導線不相交的對子。所以上述問題等價於在序列π(1),π(2),…,π(n)中找一個最長遞增子序列的問題。用書中6.6節(jié)的算法即可。假定A[1..n]是一個含n個英文字母的序列。我們希望找一個最長的子序列使得它的字母是按字母順序遞增或不降。比如，A=pacubbkdffa，它的子序列abbdff就是一個按字母順序不降的子序列。并且，它的長度是6，是一個最長的不降子序列。為方便起見，我們假定所有字母都是小寫字母。請設計一個O(n)算法找出A[1..n]中一個最長不降子序列。以A=pacubbkdffa為例，用你上述算法計算其最長不降子序列。解：(a)因為英文只有26個字母，所以任何一個不降序列必以其中一字母結尾。所以我們在掃描序列A[1..n]時，建立26個變量，S[a],S[b],…,S[z]，分別用以記錄到當前為止，我們所看到的以對應字母a，b，…，z結尾的最長不降序列的長度。并且，用I(a),I(b),…,I(z)分別記錄這些當前最長不降序列在序列A[1..n]中終止的位置。開始時S[a]=S[b]=…=S[z]=0 //邊界條件I[a]=I[b]=…=I[z]=0。 此外，我們還定義L[i]為A[1..n]中以A[i]為終止點的最長的不降序列的長度，[i]是指向子問題的指針。歸納公式如下：L[i]=1+max{S[k]|k￡A[i]} //在小于等于A[i]的字母中找一個當前最長序列Longest-Alphabet-Increasing-Subsequence(A[1..n],L,B) //B[1..L]是結果fori?atoz S[i]?I[i]?0endforfori=1ton s?0 //初始化長度 forj?atoA[i] //找max{S[k]|k￡A[i]} ifS[j]>s then s?S[j] [i]?I[j] endif endfor L[i]?1+s I[A[i]]?i //以字母A[i]結尾的最長序列一定結尾于A[i]。 S[A[i]]?L[i] //以字母A[i]結尾的不降序列的長更新endforFindksuchthatS(k)=max{S[k]|k?{a..z}} //這一步找最大S(k)L?S(k)index?I(k)forj?Ldownto1 B[j]?A[index] index?[index]endforreturnB[1..L]End 因為每次計算L[i]時最多只需檢查26個S[j]的值，所以算法復雜度為O(n)。(b)以A=pacubbkdffa為例，計算其最長不降子序列。我們得到下面表格。因為L[10]=6最大，所以L=6。由[10]=9開始往回找到這個字序列，abbdff。index1234567891011pacubbkdffaL[i]11232344562[i]00232566892S[a]12S[b]23S[c]2S[d]4S[f]56S[k]4S[p]1S[u]3B[i]abbdff(最長公共子串問題)一個字符串中的連續(xù)的一段字符序列稱為該子符串的一個字串。例如school中cho就是一個子串。子串和子序列的區(qū)別是，子序列中字符在原序列中的位置不一定連續(xù)，而子串必須連續(xù)。兩個字符串都含有的子串稱為他們的公共子串。例如，university和anniversary就含有許多公共子串，例如ni，niv，y，ers等，但最長的一個是nivers。假設有字符串X=x1x2…xn和Y=y1y2…ym，請設計一個基于動態(tài)規(guī)劃的O(mn)算法來找出X和Y的最長公共子串。解：定義l(i,j)為以X[i]和Y[j]結尾的X和Y的最長公共子串的長度。歸納公式為：l(i,j)=li-1,j-1+1如果xi=yj0否則 (1l(i,0)=0，l(0,j)=0 //初始解(1in,1jm)Longest-Common-String(X[1..n],Y[1..m],L)L?0 //初始化最長公共子串的長度fori?0ton l(i,0)?0endfor //初始解forj?0tom l(0,j)?0endfor //初始解fori?1ton forj?1tom ifX[i]=Y[j] then l(i,j)?l(i-1,j-1)+1 ifl(i,j)>L then L?l(i,j) u?i v?j endif else l(i,j)?0 endif endforendforreturnL,u,vEnd最長公共子串是以X[u]終止的X中的L個字符，即X[u-L+1]到X[u]這一段字符。算法復雜度顯然是O(nm)。如下圖(a)的例子所示，有n個多米諾骨牌，s1,s2,…,sn，按順序豎放排成一排。994911161017182117s2s1s3s4s594911101618172117s2s1s3

s4

s5

(a)(b)讓我們用U[k]和L[k]分別表示骨牌sk(1kn)豎放后上半部分數(shù)字和下半部分數(shù)字。例如，在上圖(a)的例子中，U[3]=16，L[3]=10。我們假定，在開始給定的序列里，U[k]=ak，L[k]=bk。這樣，n個上半部的數(shù)字形成一個序列，a1,a2,…,an，而n個下半部的數(shù)字也形成一個序列，b1,b2,…,bn。這兩個給定的序列不一定是排好序的。我們希望翻轉一些骨牌后使得這兩個序列都是遞增序列。我們假定min{ak,bk}min{ak+1,bk+1}，和max{ak,bk}max{ak+1,bk+1}(1kn-1)，使得這種排序是可能的。例如，上圖(b)顯示，把圖(a)中s3和s4翻轉后可使得上下兩個序列都是遞增序列。為簡單起見，設akbk。請用多級圖的方法設計一個O(n)的算法以確定最少需要翻轉幾個骨牌和哪些骨牌使得：U[1]U[2]…U[n]和L[1]L[2]…L[n]。只要求解釋圖的構造，不要求偽碼。解：我們按如下步驟構造一個多級圖：為骨牌sk(1kn)構造第k級頂點集合Vk。Vk含兩個頂點，一個代表翻轉前的狀態(tài)，另一個代表翻轉后的狀態(tài)，分別記為v(k,1)和v(k,2)。我們用U(k,1)和L(k,1)表示v(k,1)的上、下兩個數(shù)，用U(k,2)和L(k,2)表示v(k,2)的上、下兩個數(shù)。顯然有U(k,1)=ak，L(k,1)=bk，U(k,2)=bk，L(k,2)=ak。從Vk的頂點到Vk+1的頂點，1kn-1，的邊定義如下：如果U(k，1)U(k+1，1)和L(k，1)L(k+1，1)，則有邊(v(k，1),v(k+1，1)，權值為0。如果U(k，1)U(k+1，2)和L(k，1)L(k+1，2)，則有邊(v(k，1),v(k+1，2)，權值為1。如果U(k，2)U(k+1，1)和L(k，2)L(k+1，1)，則有邊(v(k，2),v(k+1，1)，權值為0。如果U(k，2)U(k+1，2)和L(k，2)L(k+1，2)，則有邊(v(k，2),v(k+1，2)，權值為1。否則沒有邊。總的原則是，相鄰兩點如果滿足排序要求，則有邊。所有指向v(k,2)的邊有權值1，因為經(jīng)過v(k,2)的路徑要求sk翻轉。其它邊有權值0。圖中加上一個源點s和它到V1的兩條邊：(s，v(1，1))權值為0，和(s，v(1，2))權值為1。圖中加上一個匯點t和Vn到t的兩條邊：(v(n，1)，t)權值為0，和(v(n，2)，t)權值為0。下圖是以題目中的骨牌序列為例構造的多級圖。顯然，任何一條從s到t的路徑給出一個滿足排序要求的骨牌序列。如果路徑經(jīng)過非初始狀態(tài)的骨牌（即下面一排的點）則表示這個骨牌要翻轉，所以路徑的總權值就等于要翻轉的骨牌的個數(shù)。因此，一條最短路徑對應一個最優(yōu)解。下圖中的最短路徑用粗線條標出?？梢姡Ds3和s4是一個最優(yōu)解。顯然，這是一個O(n)的算法。 9911v(2,1)94v(1,1)1610v(3,1)1718v(4,1)2117v(5,1)119v(2,2)

49v(1,2)1016v(3,2)

1817v(4,2)

1721v(5,2)

st0000000011111110汽車的裝配需要順序完成n步工作。假設工廠里有二條汽車裝配線，A線和B線，分別都有n個車間順序完成這n步工作。但是，A線和B線的第i個車間需要的裝配時間不同，分別為A[i]和B[i](1in)。為方便起見，A[i]和B[i]也用來作為各車間的名字。雖然我們可以選擇A[i]或B[i]來完成第i步裝配工作，但是切換到另一條線需要運輸時間，而在同一條線上則不需要運輸時間。假設從車間A[i]轉到車間B[i+1]的時間是TA[i]，而從車間B[i]轉到車間A[i+1]的時間是TB[i]。另外，從入口到A[1]車間需要時間A[0]，從入口到B[1]車間需要時間B[0]，從車間A[n]到出口需要時間A[n+1]，從車間B[n]到出口需要時間B[n+1]?，F(xiàn)在我們希望找到一條最優(yōu)的裝配流程使一部汽車從入口開始到出口為止的時間最短。這里，裝配流程是指完成這n步裝配工作的車間序列。請用動態(tài)規(guī)劃設計一個O(n)算法來找到這個最優(yōu)流程。解：這個問題可以用一個多級圖來描述。圖中起點S代表入口，終點T代表出口。兩點之間有n級頂點集合，V1，V2，…，Vn，其中Vi(1in)含兩頂點，分別代表A[i]和B[i]。從S到A[1]的邊有權A[0]，從S到B[1]的邊有權B[0]，從A[n]到T的邊有權A[n+1]，從B[n]到T的邊有權B[n+1]。另外，從Vi(1in-1)的頂點到Vi+1的頂點有4條邊。它們是，邊(A[i],A[i+1])有權值0，邊(B[i],B[i+1])有權值0，邊(A[i],B[i+1])有權值TA[i]，邊(B[i],A[i+1])有權值TB[i]。另外代表A[i]的頂點有權值A[i]，代表B[i]的頂點有權值B[i](1in)。S和T權值為0。下面的圖給出了一個n=6的例子。顯然，最優(yōu)流程對應著一條從S到T的最短路徑。與書中6.5節(jié)中多級圖不同的是，這里的路徑長度包括頂點的權值。圖中粗線標出該例子的解。另外，我們定義從入口到每個車間完成的最佳流程為一個子問題。圖中每個子問題的解標在頂點邊上。我們定義子問題的解如下：DA[i]=從S到完成A[i]的最短時間，DB[i]=從S到完成B[i]的最短時間，(1in)。那么我們有以下歸納公式：DA[1]=A[0]+A[1]， //初始解DB[1]=B[0]+B[1] //初始解DA[i]=min{DA[i-1]+A[i]，DB[i-1]+TB[i-1]+A[i]} (2in)DB[i]=min{DB[i-1]+B[i]，DA[i-1]+TA[i-1]+B[i]} (2in)。當算出DA[n]和DB[n]后，最佳解的值為D=min{DA[n]+A[n+1]，DB[n]+B[n+1]}。下面是偽碼。Shortest-Schedule(A[0..n+1,B[0..n+1],TA[1..n-1],TB[1..n-1])DA[1]A[0]+A[1]DB[1]B[0]+B[1]fori?2ton ifDA[i-1]+A[i]DB[i-1]+TB[i-1]+A[i] then DA[i]DA[i-1]+A[i] PA[i]A[i-1] //父親指針 else DA[i]DB[i-1]+TB[i-1]+A[i] PA[i]B[i-1] endif ifDB[i-1]+B[i]DA[i-1]+TA[i-1]+B[i] then DB[i]DB[i-1]+B[i] PB[i]B[i-1] else DB[i]DA[i-1]+TA[i-1]+B[i] PB[i]A[i-1] endifendforifDA[n]+A[n+1]DB[n]+B[n+1] then D?DA[n]+A[n+1] P?A[n] else D?DB[n]+B[n+1] P?B[n]endifS //準備輸出路徑，堆棧S清空Push(S,P) fork?ndownto2 ifP=A[k] thenP?PA[k] elseP?PB[k] endif Push(S,P)endforfork?1ton Pop(S) //按順序輸出經(jīng)過的車間endforEnd因為算法中每一個循環(huán)中的每一步只需要O(1)時間，而每一個循環(huán)變量最多有n個不同值，所以算法有O(n)的復雜度。假設我們有一個n個數(shù)的序列，A[1],A[2],…,A[n]，通過n-1次對兩個相鄰的數(shù)做減法后，序列變成一個數(shù)。例如，序列4,5,3,9中有4個數(shù)字。如果我們在5和3之間做減法，因為5-3=2，序列變?yōu)?,2,9。如果再取4和2做減法，得到序列2,9。最后，在2和9之間做減法，得到一個數(shù)-7。和矩陣連乘問題類似，這個過程可以用一個二叉樹表示，樹中每個內結點代表一個減法操作。例如，上面的例子可以用下面圖(a)中的二叉樹表示。讓我們把這樣一棵樹稱為減法歸約樹，而每一次減法操作稱為一次減法歸約。顯然，我們可以有許多減法歸約樹，但我們希望找到一棵最佳減法歸約樹使最后的數(shù)字最大。不難看出下面圖(b)中的二叉樹就是上面例子的最佳減法歸約樹，它產生的最后數(shù)字是11，是最大可能的結果。5(5(a)序列4,5,3,9的一棵減法歸約樹(b)序列4,5,3,9的一棵最佳減法歸約樹94322-79453211-7請設計一個動態(tài)規(guī)劃的算法為序列A[1..n]找出一棵最佳減法歸約樹，并分析你的算法的復雜度。應用你的算法算出序列5,-3,7,2,-1的一棵最佳減法歸約樹。你需要顯示每一步的細節(jié)。解：(a) 我們把計算子序列A[i],A[i+1],…,A[j](1ijn)的最佳減法歸約樹定義為一個子問題。我們定義L(i,j)為子序列A[i],A[i+1],…,A[j]的最佳減法歸約樹能產生的最大值。當i=j時，L(i,i)=A[i]。為了得到最佳減法歸約樹，我們需要考慮一個對稱的問題，即找到一個減法歸約樹使得最后的數(shù)值最小。讓我們稱題中的最佳減法歸約樹為最大歸約樹，而對稱問題中的最佳減法歸約樹為最小歸約樹。讓我們定義S(i,j)是子序列A[i],A[i+1],…,A[j](1ijn)的最小歸約樹能產生的最小值。當i=j時，S(i,i)=A[i]。我們得到下面的歸納公式：L(i,j)=maxi≤k≤j-1{Li,k-S(k+1,j)}S(i,j)=mini≤h≤j-1{S(i,h)-L(h+1,j)L(i,i)=S(i,i)=A[i]。另外，我們用K(i,j)和H(i,j)分別記彔L(i,j)和S(i,j)中的k值和h值。下面是偽碼。Max-Min-trees(A[1..n])fori=1ton L(i,i)S(i,i)A[i] //初始化endforforl1ton-1 //子問題的規(guī)模，l=j–i。 fori1to(n–l) j(i+l) L(i,j)- S(i,j)+ forkitoj-1 ifL(i,k)-S(k+1,j)>L(i,j) then L(i,j)L(i,k)-S(k+1,j) K(i,j)k endif endfor forhitoj-1 ifS(i,h)-L(h+1,j)<S(i,j) then S(i,j)S(i,h)-L(h+1,j) H(i,j)h endif endfor endforendforreturnL,S,K,Hend這個算法的復雜度顯然是O(n3)。下面是由表K和H構造最大和最小歸約樹的遞歸算法。Max-Redude-Tree(L,S,K,H,i,j)ifi=j thenconstructasinglenodepwithvalueA[i] else constructrootnodepwithvalueofL[i,j] //根結點 kK[i,j] left(p)Max-Redude-Tree(L,S,K,H,i,k) //左子樹 right(p)Min-Redude-Tree(L,S,K,H,k+1,j) //右子樹endifreturnpEndMin-Redude-Tree(L,S,K,H,i,j)ifi=j thenconstructasinglenodepwithvalueA[i] else constructrootnodepwithvalueofS[i,j] //根結點 hS[i,j] left(p)Min-Redude-Tree(L,S,K,H,i,h) //左子樹 right(p)Max-Redude-Tree(L,S,K,H,h+1,j) //右子樹endifreturnpEnd(b)序列5,-3,7,2,-1的最大歸約樹的運算L(i,j)12345S(i,j)123451581517181581-1-22-3-10-8-72-3-10-12-13375637544234235-15-1K(i,j)12345H(i,j)12345111111123322222233334333444455最大歸約樹如下：335-37-1018-132-1*假設我們有n個活動要申請使用大禮堂:S={a1,a2,…,an}。禮堂從時間t=0起可以安排?；顒觓i(1i￡n)需要連續(xù)使用的時間是ti并且在時刻di前結束，這里有0<ti￡di<￥。也就是說它必須被安排在時刻di-ti前開始，否則不可能按時完成。因為在任何時刻，兩個活動不能同時使用禮堂，所以我們只能滿足一部分活動，但我們希望能滿足盡量多的活動。請用動態(tài)規(guī)劃設計一個O(n2)算法選出集合S中最大的一個活動子集并做出它們可以不沖突地使用大禮堂的調度，也就是給出每一個被選中活動開始的時刻。(提示：先把集合S中活動按他們的結束時間di(1i￡n)排序?？杉俣╠1￡d2￡…￡dn。然后，定義子集Si={a1,a2,…,ai}(1￡i￡n)。按照動態(tài)規(guī)劃的原理，先考慮S1，再考慮S2，…，最后考慮Sn。為子集Si定義以下子問題：能否找出j個不沖突的活動？如果能，最早什么時刻可完成？我們定義M(i,j)為安排集合Si中j(1￡j￡n)個不沖突活動所需的最短時間。如果集合Si中不可能找出這j個活動，則置M(i,j)=￥。假設我們已算出M(i,j)(1￡i￡k-1,1￡j￡n)，我們該怎樣算M(k,j)(1￡j￡n)?)請用上面的算法找出下面7個話動的最優(yōu)解。A[i]1234567T[i]442.54.5635D[i]587.511.5141215

解：不妨假定d1￡d2￡…￡dn。我們稱之為時限序列。如下圖所示，在一個不沖突的活動調度中，如果aj安排在ai緊后面但是有di>dj，那么把它們交換一下后的調度仍正確。由此可假設，一組不沖突的活動可以從t=0開始，按照時限序列順序安排，并且，相鄰兩個活動之間沒有時間的間隔。讓我們定義子集Si={a1,a2,…,ai}(1￡i￡n)。再定義它的子問題：能否找出j(1￡j￡n)個不沖突的活動？如果能，最早什么時刻可完成？我們定義以下二維函數(shù)：M(i,j)=不沖突地安排集合Si中j個活動所須的最短時間(1￡j￡n)。如果不可能，例如，j>i，則置M(i,j)=￥。初始解為M(i,0)=0(1￡i￡n)，M(0,j)=￥(1￡j￡n)。 假設我們已算好M(i,j)(0￡i￡k-1,1￡j￡n)，下面要算M(k,j)(1￡j￡n)。我們需要找到遞歸公式，分析如下。 因為Sk=Sk-1{ak}，而M(k,j)是安排Sk中j個活動所需時間，那么我們有兩種方法安排這j個活動：把ak選上。那么，必須從Sk-1中選出j-1個活動并滿足條件M(k-1,j-1)+tk￡dk。不選ak。那么，必須從Sk-1中選出j個活動。如果是第一種情況，M(k,j)=M(k-1,j-1)+tk。如果是第二種情況，M(k,j)=M(k-1,j)。M(k,j)應該是兩種情況中小的那個。所以，我們有以下歸納公式：M(k,j)=min{M(k-1,j),M(k-1,j-1)+tk} 如果M(k-1,j-1)+tk￡dk，否則M(k,j)=M(k-1,j)。算完M表之后，找出最大的j使M(n,j)1￥。那么，我們最多可以安排j個活動。下面是偽碼，其中變量U[k,j]=1用來表示是第一種情況(即ak在計算M(k,j)時被選中)，U[k,j]=0是第二種情況。Schedule-Activities(A[1..n],T[1..n],D[1..n],M,U)fori?0ton M(i,0)?0 //初始解一部分endforforj?1ton M(0,j)?￥ //初始解另一部分endforfork?1ton forj?1ton ifM(k-1,j-1)+T[k]￡D[k] thent?M(k-1,j-1)+T[k] elset?￥ endif ift<M(k-1,j) then M(k,j)?t U(k,j)?1 //第1種情況，A[k]被選入M(k,j) else M(k,j)?M(k-1,j) U(k,j)?0 endif endforendforj?1 //找最大的j使M[n,j]非無窮大whileM(n,j)1￥andj￡n //一旦M(n,j)=￥，那么M(n,j+1)更是￥ j?j+1endwhilej?j–1 //最優(yōu)解有j個活動t?M(n,j) k?n //從A[n]開始，輸出這j個活動whilej>0 ifU(k,j)=1 then scheduleA[k]from(t–T[k])tot //安排A[k]在最后面，到t為止 t?(t–T[k]) j?j–1 //還有j-1個活動需安排 endif k?k–1 //下面考慮Sk-1和M(k-1,j)，如果U(k,j)=1，則j已更新為j-1endwhileEnd算法的復雜度顯然是O(n2)。用上面的算法找出下面7個話動的最優(yōu)解。A[i]1234567T[i]442.54.5635D[i]587.511.5141215按結束時間排序后得到：A[i]1234567T[i]42.544.5365D[i]57.5811.5121415表M和表U計算如下(兩表合一)M(i,j)/U(i,j)01234567原序號00￥￥￥￥￥￥￥104/1￥￥￥￥￥￥302.5/16.5/1￥￥￥￥￥202.5/06.5/0￥￥￥￥￥402.5/06.5/011/1￥￥￥￥602.5/05.5/19.5/1￥￥￥￥502.5/05.5/09.5/0￥￥￥￥702.5/05.5/09.5/014.5/1￥￥￥被調度的活動是A[1]，A[3]，A[6]，A[7](原序號)。表中陰影部分顯示的是從最右邊非無窮大M(n,j)開始往回找出j個活動的路線。實際調度如下圖。假設你有n尺的一卷布要賣。你可以整卷賣，也可以裁為幾段賣，但每段必須是整數(shù)尺。假定從1尺長到n尺長的各種長度的價格都已定好為P[i](1￡i￡n)?，F(xiàn)在希望找到一個裁剪方案使總的賣價最大。例如，下面表格顯示從1尺到6尺的價格(n=6)，那么，如果把這6尺布裁為2尺和4尺兩段，則可賣出4+7=11元。如果裁為3段，每段2尺，則可賣出34=12元，而不裁整賣卻只值9元。長i(尺)123456價格pi(元)144789請用動態(tài)規(guī)劃設計一算法來計算如何裁開(或不裁開)這n尺布使得總的賣價最大。請給出偽碼和它的復雜度。解: 設一段有i尺長的布裁開或不裁開所能得到的最大賣價為R[i]。當i=n時，R[n]即是答案。我們用動態(tài)規(guī)劃方法求R[i]。以下是歸納公式：R[1]=P[1] (初始解，i=1)。R[i]=max{max1≤k≤i-1Rk+Ri-k,P 因為裁為兩段長為a和b也就是b和a，所以歸納公式可改進為：R[1]=P[1] (初始解，i=1)。R[i]=max{max1≤k≤i/2Rk+Ri-k我們用C[i]表示第一刀應從那里剪開。根據(jù)這個公式，題目中例子的解如下，其中nil表示不裁開賣為最佳：i123456R[i](元)1458912C[i](尺)nilnil1212偽碼如下。Cloth-Cutting(P,n)R[1]?P[1]fori?2ton q?P[i] //整賣i尺布的價錢 C[i]?nil fork?1to?i/2? ifq<R[k]+R[i-k] then q?R[k]+R[i-k] C[i]?k endif endforendforreturnR,CEnd 該算法復雜度顯然是O(n2)。假設有n個硬幣排成一個序列V[1..n]，其幣值依次為V[1]，V[2]，…，V[n]。兩個玩游戲的人輪流從序列中取走一個硬幣，但每次只能取序列頭尾兩端的硬幣之一，而不能從序列中間取。假設你和對手玩這個游戲，而且你走第一步。用動態(tài)規(guī)劃設計一個O(n2)算法使你在最壞情況下能取走硬幣的總幣值最大。這里，最壞情況是指對手和你一樣聰明。請給出歸納公式和初始解，不要求偽碼。用你上面(a)部分算法對序列V[1..5]=<5,2,8,3,6>進行運算，顯示每步結果。解：(a)定義M(i,j)=走第一步的人在最壞情況下能從子序列V[i..j]中取走硬幣的最大總幣值。定義W(i,j)=k=ijV[k]，即子序列V[i..jM(i,i)=V[i]， (初始解，i=1,2,…,n)M(i,j)=W(i,j)–min{W(i+1,j),W(i,j-1)} 如果i<j。這是因為，你只有兩種選擇，取子序列中第一個硬幣或最后一個。如果你取走第一個硬幣，對手面臨子序列V[i+1..j]，否則對手面臨子序列V[i..j-1]。因為最壞情況下，對手會分別取走總幣值W(i+1,j)或W(i,j-1)，因此，讓對手取走其中小者是最好的結果。所以，在最壞情況下，走第一步的人最多可得M(i,j)=W(i,j)–min{W(i+1,j),W(i,j-1)}。我們用K(i,j)記錄第一步的人取的是頭還是尾，所以有：如果W(i+1,j)≤W(i,j-1),那么K(i,j)=i，否則K(i,j)=j。算法顯然有O(n2)復雜度。(b)用上面(a)部分算法對序列V[1..5]=<5,2,8,3,6>進行運算。W(i,j)12345M(i,j)1234515715182415510131122101319228514381117388114394365656K(i,j)12345113152345333455下面的二叉樹描述了這個解中二人取硬幣的過程。從這個例子中可見，先走第一步的人不一定比后走的拿到更大總幣值。242418261351038第3步取走V[4]=3第5步取走V[2]=2第2步取走V[1]=5第1步取走V[5]=6開始總價值=W(1,5)W(2,4)W(1,4)W(2,3)第4步取走V[3]=8重新做18題，但不同的是，這次我們考慮最好情況，即假設對手很苯，每次都走錯，而且你仍然走第一步。解：(a)定義M(i,j)=走第一步的人在最好情況下能從子序列V[i..j]中取走硬幣的最大總幣值。歸納公式為：M(i,i)=V[i]， (初始解一部分，j=i=1,2,…,n)M(i,i+1)=max{V[i]，V[i+1]} (初始解另一部分，j=i+1，i=1,2,…,n-1)M(i,j)=max{M(i+2,j)+V[i],M(i+1,j-1)+V[i],M(i+1,j-1)+V[j],M(i,j-2)+V[j]} 如果j>i+1。這是因為，你能得到最好的結果的前提是，對手在下一步得到最差的結果。所以，算法在每一步確定兩個硬幣，一個是你拿的，另一個是給對手拿的。我們用K(i,j)記錄第1步你取的是頭還是尾，而用U(i,j)記錄對手在第2步應該取的硬幣。具體操作如下：如果M(i,j)=M(i+2,j)+V[i]，則K(i,j)=i，U(i,j)=i+1;如果M(i,j)=M(i+1,j-1)+V[i]，則K(i,j)=i，U(i,j)=j;如果M(i,j)=M(i+1,j-1)+V[j]，則K(i,j)=j，U(i,j)=i;如果M(i,j)=M(i,j-2)+V[j]，則K(i,j)=j，U(i,j)=j-1。算法顯然有O(n2)復雜度。(b)用上面(a)部分算法對序列5,2,8,3,6進行運算。M(i,j)1234515513131922811143881443656K(i,j)12345U(i,j)12345113151222423452222333344454455下面的二叉樹描述了這個解中二人取硬幣的過程。151550第3步你取走V[1]=5，對手無硬幣可取。第1步你取走V[5]=6，對手取V[4]=3開始時總價值W(1,5)W(1,3)246+38+25W(1,1)第2步你取走V[3]=8，對手取V[2]=3有n個硬幣排成一列，分別有幣值c1,c2,...,cn。這些幣值也許有相同的，但都是正數(shù)。設計一個O(n)的算法選取出一組不相鄰的硬幣使得總幣值最大。不相鄰的意思是，選出的硬幣在原序列中不相鄰。你只需定義子問題的集合和設計歸納公式。不要求偽碼。用上面(a)部分的算法為下面的幣值序列選取一組不相鄰的硬幣使得總幣值最大。要求顯示每一步的結果。<c1,c2,c3,c4,c5,c6,c7,c8>=<4,14,7,3,13,5,9,7>。解： (a) 我們定義子集Ci={c1,c2,...,ci}(1in)。對應于Ci的子問題是，從Ci中選取出一組不相鄰的硬幣使得總幣值最大。我們定義：F(i)=Ci中一組不相鄰的硬幣可能有的最大總幣值。我們有如下歸納公式：F(0)=0,F(1)=c1 (初始解) F(i)=max{ci+F(k-2),F(k-1)} 如果i≥2。 用上面(a)部分的算法于下面的幣值序列。<c1,c2,c3,c4,c5,c6,c7,c8>=<4,14,7,3,13,5,9,7>每步的結果顯示于下面的表中。序號i012345678C(i)4147313597F(i)0414141727273636選擇+F(0)+F(0)F(2)+F(2)+F(3)F(5)+F(5)F(7)表中，如果第i列的選擇是+F(k)，則表示F(i)選中硬幣C(i)，再加上F(k)。如果第i列的選擇是F(k)，則表示解F(i)不選硬幣C(i)，F(xiàn)(i)=F(k)。上面例子的解是：C(7),C(5),C(2)，總價值是36。兩個人的游戲中有兩摞硬幣。其中一摞有n個，從下向上分別有幣值A[1],A[2],…,A[n]，存于數(shù)組A[1..n]。另一摞有m個，從下向上分別有幣值B[1],B[2],…,B[m]，存于數(shù)組B[1..m]。假設幣值都是正數(shù)。兩個游戲者輪流從這兩摞硬幣中每次取走一枚硬幣直到取完。規(guī)定每次只能取兩摞中其中一摞的最上面的一枚硬幣，不允許不取或從中間取。游戲前，所有幣值都已知。用動態(tài)規(guī)劃設計一個O(mn)算法以求出第一個取硬幣的人在最壞情況時能得到的最大總幣值。最壞情況是指對方和你一樣聰明，每次都能正確地取走硬幣使他的總幣值最大化。你需要給出歸納公式和初始條件。偽碼可略去。用(a)中的算法對以下兩個幣值序列求出第一個玩游戲的人在最壞情況時能得到的最大總幣值。A[1..6]=<4,12,6,10,3,8>,B[1..5]=<13,9,1,5,7>。解：(a)定義子序列A[1..i]和B[1..j](1in,1jm)。那么對應的子問題是，給定兩摞硬幣，A[1..i]和B[1..j]，求出第一個取硬幣的人在最壞情況時能得到的最大總幣值。我們定義M(i,j)為這個最大總幣值。再定義：W(0,j)=k=1jB[k]，W(i,0)=k=1iAk，W(i,j)=W(0,j)+我們有以下初始解：M(0,0)=0 (初始解，i=0和j=0)。歸納公式如下，我們用K(i,j)來記錄應當取走的硬幣：M(0,j)=W(0,j)–M(0,j-1)，K(i,j)=B[j] (i=0和j>0)，M(i,0)=W(i,0)–M(i-1,0)，K(i,j)=A[i] (i>0和j=0)，M(i,j)=W(i,j)–min{M(i-1,j),M(i,j-1)} 如果i>0和j>0。如果M(i-1,j)≤M(i,j-1)，則有K(i,j)=A[i]，否則K(i,j)=B[j]。用(a)中的算法求解以下兩序列：A[1..6]=<4,12,6,10,3,8>,B[1..5]=<13,9,1,5,7>。W(i,j)01234500132223283514172627323921629383944513223544455057432455455606753548575863706435665667178fM(i,j)012345K012345001391414210-BBBBB1413171319201ABAABB21217212625312ABAAAA31025232228293ABABBB42223313332384ABAAAA51335263231395ABABAB63026393440396ABAAAA 取幣序號 1234567891011總值游戲者1A[6]8A[5]3B[4]5A[3]6A[1]4B[1]1339游戲者2B[5]7A[4]10B[3]1A[2]12B[2]939一塊寬為L的長方形電路板的上邊有m個端口，它們與電路板左端的距離分別為U[1],U[2],…,U[m]。電路板的下邊有n個端口，它們與電路板左端的距離分別為L[1],L[2],…,L[n],n<m?，F(xiàn)在需要在上面的m個端口中選出n個端口，分別與下邊的n個端口用導線連接，并要求這n條導線的總長最小。下圖給出了一個m=8，n=4的示意圖。證明在一個最佳解中，任意兩個連線不會相交。為上述問題設計一個O(mn)的動態(tài)規(guī)劃的算法。解:我們用反證法證明。我們用(i,j)和d(i,j)分別表示點U[i]和L[j]之間的線段及其距離。假設在一個最佳解中，有兩個線段，(i,j)和(u,v)相交。那么，如下圖(b)所示，U[i]、U[u]、L[j]、L[v]四點形成一個四邊形。其兩對角線長度之和大于其對邊長之和，故有d(i,j)+d(u,v)>d(i,v)+d(u,j)。這就是說，把這兩線段換為(i,v)和(u,j)后，可得到一個更好的解，與最佳解矛盾。我們考慮如下子問題：假設上邊的可用端口為U[1],U[2],…,U[i](im)。而下邊需要連接的端口是L[1],L[2],…,L[j](jn,ji)?，F(xiàn)在需要在上面的i個端口中選出j個端口，分別與下邊的j個端口用導線連接，并要求這j條導線的總長最小。顯然，當i=m，j=n時，該子問題就是原問題。我們定義d(i,j)=Ui-L[j]2+L2為點U[i]和L[j]之間的距離，定義這個子問題的最佳解的j條導線的總長是MMM(i,0)=0 (初始解，i=0,1,…,m)。如果M(i,j)=M(i-1,j)，記K(i,j)=F，否則，記K(i,j)=T。偽碼如下：Segment-Selection(U[1..m],L[1..n],M,K)fori0tom M(i,0)0endif //初始解forj1ton fori1toj-1 M(i,j) endfor forijtom ifM(i-1,j)d(i,j)+M(i-1,j-1), then M(i,j)M(i-1,j) K(i,j)=F else M(i,j)M(i-1,j-1)+d(i,j) K(i,j)=T endif endforendforimforjndownto1 //輸出結果 whileK(i,j)=F ii-1 endwhile outputpair(i,j) //連結U[i]和L[j] ii–1endforEnd //M(m,n)是總長顯然這是一個O(mn)算法。假設在一個n