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

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

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

找出下面二序列的最長(zhǎng)公共子序列：<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>，其長(zhǎng)度為6。下面表中列出了搜索7個(gè)關(guān)鍵字A[1..7]的各種情況的概率。請(qǐng)為他們找出一個(gè)最佳二元搜索樹(shù)并求出其平均復(fù)雜度。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這個(gè)最佳二元搜索樹(shù)如下。它的平均復(fù)雜度是3.12次比較。AA[5]A[2]A[1]A[3]A[6]A[7]d0d1d2d3d4A[4]d6d5d7給出一個(gè)在序列A[1..n]中找最長(zhǎng)遞增子序列的O(nlgn)算法的偽碼。解： Improved-LCS(A[1..n],L,B,length)L?L[1]?1 //當(dāng)前只有一個(gè)長(zhǎng)度l=1的初始解[1]?nil //父親未知S[0]?A[0]- //因二元搜索的需要，加的一個(gè)左邊點(diǎn)T[0]?0 //S[0]在序列A中的序號(hào)S[1]?A[1] //長(zhǎng)度為1的子序列的結(jié)尾元素開(kāi)始只有A[1]T[1]?1 //S[1]在序列A中的序號(hào)S[L+1]? //因二元搜索的需要，加的一個(gè)右邊點(diǎn)fori=2ton Binary-search(S,0,L+1,A[i],k) //調(diào)用二元搜索子程序，其偽碼在后面。 //找出k使得S[k]A[i]<S[k+1]，見(jiàn)下面?zhèn)未a。 L[i]?k+1 //L[i]長(zhǎng)度必為k+1 [i]?T[k] //A[i]接在A[j]后面，這里[i]=j=T[k] S[k+1]?A[i] //因?yàn)锳[i]<S[k+1],更新S[k+1] T[k+1]?i //同時(shí)更新對(duì)應(yīng)的序號(hào) ifL[i]>L then L?L+1 S[L+1]? //多了一個(gè)長(zhǎng)度 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) //輸入時(shí)有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假設(shè)我們要將一根大型長(zhǎng)鋼管鋸成若干段。我們?cè)谝彽牡胤酱蛏蠘?biāo)記，一共是n個(gè)標(biāo)記。這些標(biāo)記距離鋼管左端的距離，從左到右，分別是a1，a2，…，an厘米。這個(gè)鋼管的總長(zhǎng)是l厘米，l>an(參見(jiàn)下圖)。當(dāng)我們將鋼管鋸為兩截時(shí)，需要的代價(jià)與當(dāng)時(shí)被鋸鋼管的長(zhǎng)度成正比，比例是每一厘米p元。請(qǐng)用動(dòng)態(tài)規(guī)劃設(shè)計(jì)一個(gè)算法，找出最優(yōu)的順序來(lái)完成這n處的切割并使總的代價(jià)最小。分析你的算法的復(fù)雜度。(提示：用a0=0和an+1=l表示鋼管左端和右端位置。用[ai,aj]表示從標(biāo)記ai到標(biāo)記aj這段鋼管。用C(i,j)表示完成對(duì)[ai,aj]這段鋼管的切割任務(wù)所需的最小代價(jià)，也就是完成所有ak(i<k<j)處的切割所需代價(jià)。找出C(i,j)的歸納公式。)以下面數(shù)據(jù)為例，用你在(a)中的算法找出最優(yōu)的切割順序和總代價(jià)。請(qǐng)顯示你的計(jì)算過(guò)程。a1=2，a2=5，a3=9，a4=14，l=15，p=1。解：(a) 定義C(i,j)=切割鋼管[ai,aj]（子問(wèn)題）所需最小代價(jià)。我們有以下歸納公式：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是子問(wèn)題的規(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上面算法的復(fù)雜度顯然是O(n3)。(b) a1=2,a2=5,a3=9,a4=14,l=15,p=1。表C、表S和表示順序的二叉樹(shù)構(gòu)造如下，總的代價(jià)是35元。a1a1a2a3a4a3a2a4a1如下圖所示，順序放好的n根鋼管的重量順序?yàn)閃[i](1￡i￡n)。我們需要把他們依照順序焊成一根鋼管，但每次焊接可任意選兩根相鄰的鋼管來(lái)焊接。每次焊接的代價(jià)與被焊兩段鋼管的總重量成正比。為簡(jiǎn)單起見(jiàn)，把代價(jià)定為被焊兩段鋼管的總重量。例如，W[1]=5,W[2]=1,W[3]=2，如果先把W[1]和W[2]焊好，代價(jià)為5+1=6。焊好的這塊有重量6，再把W[3]焊上，又要代價(jià)6+2=8，總代價(jià)是14。但如果先焊W[2]和W[3]，再焊W[1]，則總代價(jià)為11。用動(dòng)態(tài)規(guī)劃設(shè)計(jì)一個(gè)算法，計(jì)算出最優(yōu)的焊接順序使總代價(jià)最小。應(yīng)用你上面的算法求出以下5根鋼管的最優(yōu)焊接順序和總代價(jià)：W[1]=8,W[2]=1,W[3]=7,W[4]=2,W[5]=9。解：(a) 我們用[ai,aj]表示把從ai到aj這一段的鋼管焊好后的鋼管。找[ai,aj]的最優(yōu)焊接順序定義為子問(wèn)題。我們定義C(i,j)=將鋼管[ai,aj]焊好的最小代價(jià)(子問(wèn)題的解，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]分為兩段的地方，也就是最后一次應(yīng)焊的位置。表W(i,j)(1￡i￡j￡n)可以先計(jì)算好。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)焊接順序由下面二叉樹(shù)表示。總代價(jià)為62(=8+16+11+27)。如下圖所示，順序放好的n根鋼管的重量順序?yàn)閃[i](1￡i￡n)。我們需要把他們依照順序焊成一根鋼管，但每次焊接可任意選兩根相鄰的鋼管來(lái)焊接。每次焊接的代價(jià)與被焊兩段鋼管中的較重的一根的重量成正比。為簡(jiǎn)單起見(jiàn)，就把代價(jià)定為被焊兩段鋼管中的較重的一根的重量。例如，W[1]=5,W[2]=1,W[3]=2，如果先把W[1]和W[2]焊好，代價(jià)為5，再把W[3]焊上，又要代價(jià)6，總代價(jià)是11。但如果先焊W[2]和W[3]，再焊W[1]，則總代價(jià)為2+5=7。用動(dòng)態(tài)規(guī)劃設(shè)計(jì)一個(gè)算法，計(jì)算出最優(yōu)的焊接順序使總代價(jià)最小。應(yīng)用你上面的算法求出以下5根鋼管的最優(yōu)焊接順序和總代價(jià)：W[1]=6,W[2]=2,W[3]=7,W[4]=5,W[5]=8。解：(a) 我們用[ai,aj]表示把從ai到aj這一段的鋼管焊好后的鋼管。找[ai,aj]的最優(yōu)焊接順序定義為子問(wèn)題。定義C(i,j)=將鋼管[ai,aj]焊好的最小代價(jià)(子問(wèn)題的解，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]分為兩段的地方，也就是最后一次應(yīng)焊的位置。表W(i,j)(1￡i￡j￡n)可以先計(jì)算好。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)焊接順序由下面二叉樹(shù)表示。總代價(jià)為37(=6+8+8+15)。假設(shè)一通訊公司要設(shè)計(jì)一個(gè)n路的復(fù)用器。它把n條平行的輸入線路并入到一條輸出線路。這個(gè)復(fù)用的過(guò)程是逐步實(shí)現(xiàn)的。它每次把相鄰的兩條線路并為一條輸出線路。如果這兩條線路的帶寬分別是a和b的話，那么合并后的輸出線路有帶寬a+b。經(jīng)過(guò)一系列兩兩合并后，我們得到一條輸出線路，它的帶寬是所有輸入帶寬之和。下面的圖給出n=5的一個(gè)例子。我們假定在合并兩條帶寬分別是a和b的線路時(shí)的硬件代價(jià)為a+b。下圖例子中的設(shè)計(jì)需要的硬件總代價(jià)是25+27+37+64=153。MUXMUXMUXMUXMUXW1=10W2=15W3=12W4=18W5=9W=25W=37W=27W=64n-wayMUX假設(shè)這n條輸入線路的帶寬依次為W1，W2，…，Wn，用動(dòng)態(tài)規(guī)劃設(shè)計(jì)一個(gè)算法來(lái)確定最優(yōu)的合并順序以使硬件總代價(jià)最小。應(yīng)用你的算法為下列帶寬序列確定合并的最佳順序并給出硬件總代價(jià)：W[1]=13,W[2]=21,W[3]=17,W[4]=12,W[5]=25。解：(a)這道題和第6題做法一樣。定義C(i,j)=將Wi到Wj之間所有線路合并的最小代價(jià)(子問(wèn)題的解，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)時(shí)得的k值。表W(i,j)(1￡i￡j￡n)可以用下面子程序Bandwidth(W,n)先計(jì)算好。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(jià)為34+29+54+88=205。MUXMUXMUXMUXMUXW1=13W2=21W3=17W4=12W5=25W=34W=54W=29W=88假設(shè)我們有三個(gè)字母或數(shù)字的序列，X[1..m]=x1x2...xm，Y[1..n]=y1y2...yn，和Z[1..m+n]=z1z2...zm+n。如果序列Z是由X和Y中的元素按順序交匯而成，那么Z被稱為X和Y的一個(gè)洗牌。例如，下面圖中的序列Z=cchocohilaptes是X=chocolate和Y=chips的一個(gè)洗牌。 YY=chipsX=chocolateZ=cchocohilaptes用動(dòng)態(tài)規(guī)劃設(shè)計(jì)一個(gè)算法來(lái)確定序列Z是否是X和Y的一個(gè)洗牌。(提示：用M[i,j]=1表示Z[1..i+j]是X[1..i]和Y[1..j]的一個(gè)洗牌。然后找出歸納公式。)用你的算法確定以下三序列中，Z是否是X和Y的一個(gè)洗牌。X=FEAST, Y=LOVE, Z=FLOEVASET解一：有個(gè)簡(jiǎn)單的方法是先求X和Z的最長(zhǎng)公共子序列W。如果WX，則Z不可能是X和Y的一個(gè)洗牌。如果W=X，檢查把X從Z中刪去后的序列是否等于Y。如果是，則Z是解二：(a) 我們建一個(gè)表M，其中M[i,j]=1(1im,1jn)表示Z[1..i+j]是X[1..i]和Y[1..j]的一個(gè)洗牌。我們有以下歸納公式。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的一個(gè)洗牌。偽碼如下。Shuffle(X[1..m],Y[1..n],Z[1..m+n]，M，D) //D[i,j]是指向子問(wèn)題的指針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算法顯然有復(fù)雜度O(mn)。算法中表D可省略，但如果要知道Z是如何洗牌得到的，那么可從D得到。(b)X=FEAST, Y=LOVE, Z=FLOEVASET。表MY[j]LOVEX[i]01234010000F111100E200110A300010S400011T500001由上表知Z是X和Y的一個(gè)洗牌。一塊長(zhǎng)方形電路板的上下兩邊各有n個(gè)端口并用數(shù)字順序標(biāo)為1，2，3，…，n。根據(jù)電路設(shè)計(jì)的要求，我們需要把上邊的n個(gè)端口和下邊的n個(gè)端口一一配對(duì)后用導(dǎo)線連接。假設(shè)與上邊第i個(gè)端口號(hào)連接的下邊的端口號(hào)是π(i)，那么要連接的n個(gè)對(duì)子為(i,π(i))(1≤i≤n)。下面的圖給出了一個(gè)n=8的例子。在這個(gè)例子中，我們有π(1)=3，π(2)=1，π(3)=6，π(4)=8，π(5)=2，π(6)=5，π(7)=4，π(8)=7?，F(xiàn)在需要把這些對(duì)子分組使得在一組里的導(dǎo)線不相交從而可以分布在同一個(gè)絕緣層上。比如，在下圖中，連接對(duì)子(1,3),(3,6),(4,8)的導(dǎo)線是不相交的。如何用最少的組數(shù)把它們分開(kāi)是個(gè)有趣的問(wèn)題但不在此討論?，F(xiàn)在的問(wèn)題是，我們只找一組導(dǎo)線不相交的對(duì)子集合，使得它含有的對(duì)子最多。比如在下圖中，{(2,1),(5,2),(6,5),(8,7)}就是最大的一組導(dǎo)線不相交的對(duì)子集合，它含有4個(gè)導(dǎo)線不相交的對(duì)子。請(qǐng)用最長(zhǎng)遞增子序列算法里的方法設(shè)計(jì)一個(gè)O(n2)算法來(lái)找出一組最大的導(dǎo)線不相交的對(duì)子集合。解：我們注意到，如果有一組導(dǎo)線不相交的對(duì)子，(i1,π(i1)),(i2,π(i2)),…,(ik,π(ik))，其中i1<i2<…<ik，因?yàn)樗麄兊膶?dǎo)線都不相交，那么我們必須有π(i1)<π(i2)<…<π(ik)。也就是說(shuō)，這些電路板下方的端口號(hào)是一個(gè)遞增序列。反過(guò)來(lái)，如果在序列,π(1),π(2),…,π(n)中有一個(gè)遞增子序列，π(i1)<π(i2)<…<π(ik)，那么{(i1,π(i1)),(i2,π(i2)),…,(ik,π(ik))}就一定是一組導(dǎo)線不相交的對(duì)子。所以上述問(wèn)題等價(jià)於在序列π(1),π(2),…,π(n)中找一個(gè)最長(zhǎng)遞增子序列的問(wèn)題。用書(shū)中6.6節(jié)的算法即可。假定A[1..n]是一個(gè)含n個(gè)英文字母的序列。我們希望找一個(gè)最長(zhǎng)的子序列使得它的字母是按字母順序遞增或不降。比如，A=pacubbkdffa，它的子序列abbdff就是一個(gè)按字母順序不降的子序列。并且，它的長(zhǎng)度是6，是一個(gè)最長(zhǎng)的不降子序列。為方便起見(jiàn)，我們假定所有字母都是小寫(xiě)字母。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n)算法找出A[1..n]中一個(gè)最長(zhǎng)不降子序列。以A=pacubbkdffa為例，用你上述算法計(jì)算其最長(zhǎng)不降子序列。解：(a)因?yàn)橛⑽闹挥?6個(gè)字母，所以任何一個(gè)不降序列必以其中一字母結(jié)尾。所以我們?cè)趻呙栊蛄蠥[1..n]時(shí)，建立26個(gè)變量，S[a],S[b],…,S[z]，分別用以記錄到當(dāng)前為止，我們所看到的以對(duì)應(yīng)字母a，b，…，z結(jié)尾的最長(zhǎng)不降序列的長(zhǎng)度。并且，用I(a),I(b),…,I(z)分別記錄這些當(dāng)前最長(zhǎng)不降序列在序列A[1..n]中終止的位置。開(kāi)始時(shí)S[a]=S[b]=…=S[z]=0 //邊界條件I[a]=I[b]=…=I[z]=0。 此外，我們還定義L[i]為A[1..n]中以A[i]為終止點(diǎn)的最長(zhǎng)的不降序列的長(zhǎng)度，[i]是指向子問(wèn)題的指針。歸納公式如下：L[i]=1+max{S[k]|k￡A[i]} //在小于等于A[i]的字母中找一個(gè)當(dāng)前最長(zhǎng)序列Longest-Alphabet-Increasing-Subsequence(A[1..n],L,B) //B[1..L]是結(jié)果fori?atoz S[i]?I[i]?0endforfori=1ton s?0 //初始化長(zhǎng)度 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]結(jié)尾的最長(zhǎng)序列一定結(jié)尾于A[i]。 S[A[i]]?L[i] //以字母A[i]結(jié)尾的不降序列的長(zhǎng)更新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 因?yàn)槊看斡?jì)算L[i]時(shí)最多只需檢查26個(gè)S[j]的值，所以算法復(fù)雜度為O(n)。(b)以A=pacubbkdffa為例，計(jì)算其最長(zhǎng)不降子序列。我們得到下面表格。因?yàn)長(zhǎng)[10]=6最大，所以L=6。由[10]=9開(kāi)始往回找到這個(gè)字序列，abbdff。index1234567891011pacubbkdffaL[i]11232344562[i]00232566892S[a]12S[b]23S[c]2S[d]4S[f]56S[k]4S[p]1S[u]3B[i]abbdff(最長(zhǎng)公共子串問(wèn)題)一個(gè)字符串中的連續(xù)的一段字符序列稱為該子符串的一個(gè)字串。例如school中cho就是一個(gè)子串。子串和子序列的區(qū)別是，子序列中字符在原序列中的位置不一定連續(xù)，而子串必須連續(xù)。兩個(gè)字符串都含有的子串稱為他們的公共子串。例如，university和anniversary就含有許多公共子串，例如ni，niv，y，ers等，但最長(zhǎng)的一個(gè)是nivers。假設(shè)有字符串X=x1x2…xn和Y=y1y2…ym，請(qǐng)?jiān)O(shè)計(jì)一個(gè)基于動(dòng)態(tài)規(guī)劃的O(mn)算法來(lái)找出X和Y的最長(zhǎng)公共子串。解：定義l(i,j)為以X[i]和Y[j]結(jié)尾的X和Y的最長(zhǎng)公共子串的長(zhǎng)度。歸納公式為：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 //初始化最長(zhǎng)公共子串的長(zhǎng)度f(wàn)ori?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最長(zhǎng)公共子串是以X[u]終止的X中的L個(gè)字符，即X[u-L+1]到X[u]這一段字符。算法復(fù)雜度顯然是O(nm)。如下圖(a)的例子所示，有n個(gè)多米諾骨牌，s1,s2,…,sn，按順序豎放排成一排。994911161017182117s2s1s3s4s594911101618172117s2s1s3

s4

s5

(a)(b)讓我們用U[k]和L[k]分別表示骨牌sk(1kn)豎放后上半部分?jǐn)?shù)字和下半部分?jǐn)?shù)字。例如，在上圖(a)的例子中，U[3]=16，L[3]=10。我們假定，在開(kāi)始給定的序列里，U[k]=ak，L[k]=bk。這樣，n個(gè)上半部的數(shù)字形成一個(gè)序列，a1,a2,…,an，而n個(gè)下半部的數(shù)字也形成一個(gè)序列，b1,b2,…,bn。這兩個(gè)給定的序列不一定是排好序的。我們希望翻轉(zhuǎn)一些骨牌后使得這兩個(gè)序列都是遞增序列。我們假定min{ak,bk}min{ak+1,bk+1}，和max{ak,bk}max{ak+1,bk+1}(1kn-1)，使得這種排序是可能的。例如，上圖(b)顯示，把圖(a)中s3和s4翻轉(zhuǎn)后可使得上下兩個(gè)序列都是遞增序列。為簡(jiǎn)單起見(jiàn)，設(shè)akbk。請(qǐng)用多級(jí)圖的方法設(shè)計(jì)一個(gè)O(n)的算法以確定最少需要翻轉(zhuǎn)幾個(gè)骨牌和哪些骨牌使得：U[1]U[2]…U[n]和L[1]L[2]…L[n]。只要求解釋圖的構(gòu)造，不要求偽碼。解：我們按如下步驟構(gòu)造一個(gè)多級(jí)圖：為骨牌sk(1kn)構(gòu)造第k級(jí)頂點(diǎn)集合Vk。Vk含兩個(gè)頂點(diǎn)，一個(gè)代表翻轉(zhuǎn)前的狀態(tài)，另一個(gè)代表翻轉(zhuǎn)后的狀態(tài)，分別記為v(k,1)和v(k,2)。我們用U(k,1)和L(k,1)表示v(k,1)的上、下兩個(gè)數(shù)，用U(k,2)和L(k,2)表示v(k,2)的上、下兩個(gè)數(shù)。顯然有U(k,1)=ak，L(k,1)=bk，U(k,2)=bk，L(k,2)=ak。從Vk的頂點(diǎn)到Vk+1的頂點(diǎn)，1kn-1，的邊定義如下：如果U(k，1)U(k+1，1)和L(k，1)L(k+1，1)，則有邊(v(k，1),v(k+1，1)，權(quán)值為0。如果U(k，1)U(k+1，2)和L(k，1)L(k+1，2)，則有邊(v(k，1),v(k+1，2)，權(quán)值為1。如果U(k，2)U(k+1，1)和L(k，2)L(k+1，1)，則有邊(v(k，2),v(k+1，1)，權(quán)值為0。如果U(k，2)U(k+1，2)和L(k，2)L(k+1，2)，則有邊(v(k，2),v(k+1，2)，權(quán)值為1。否則沒(méi)有邊。總的原則是，相鄰兩點(diǎn)如果滿足排序要求，則有邊。所有指向v(k,2)的邊有權(quán)值1，因?yàn)榻?jīng)過(guò)v(k,2)的路徑要求sk翻轉(zhuǎn)。其它邊有權(quán)值0。圖中加上一個(gè)源點(diǎn)s和它到V1的兩條邊：(s，v(1，1))權(quán)值為0，和(s，v(1，2))權(quán)值為1。圖中加上一個(gè)匯點(diǎn)t和Vn到t的兩條邊：(v(n，1)，t)權(quán)值為0，和(v(n，2)，t)權(quán)值為0。下圖是以題目中的骨牌序列為例構(gòu)造的多級(jí)圖。顯然，任何一條從s到t的路徑給出一個(gè)滿足排序要求的骨牌序列。如果路徑經(jīng)過(guò)非初始狀態(tài)的骨牌（即下面一排的點(diǎn)）則表示這個(gè)骨牌要翻轉(zhuǎn)，所以路徑的總權(quán)值就等于要翻轉(zhuǎn)的骨牌的個(gè)數(shù)。因此，一條最短路徑對(duì)應(yīng)一個(gè)最優(yōu)解。下圖中的最短路徑用粗線條標(biāo)出?？梢?jiàn)，翻轉(zhuǎn)s3和s4是一個(gè)最優(yōu)解。顯然，這是一個(gè)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步工作。假設(shè)工廠里有二條汽車裝配線，A線和B線，分別都有n個(gè)車間順序完成這n步工作。但是，A線和B線的第i個(gè)車間需要的裝配時(shí)間不同，分別為A[i]和B[i](1in)。為方便起見(jiàn)，A[i]和B[i]也用來(lái)作為各車間的名字。雖然我們可以選擇A[i]或B[i]來(lái)完成第i步裝配工作，但是切換到另一條線需要運(yùn)輸時(shí)間，而在同一條線上則不需要運(yùn)輸時(shí)間。假設(shè)從車間A[i]轉(zhuǎn)到車間B[i+1]的時(shí)間是TA[i]，而從車間B[i]轉(zhuǎn)到車間A[i+1]的時(shí)間是TB[i]。另外，從入口到A[1]車間需要時(shí)間A[0]，從入口到B[1]車間需要時(shí)間B[0]，從車間A[n]到出口需要時(shí)間A[n+1]，從車間B[n]到出口需要時(shí)間B[n+1]。現(xiàn)在我們希望找到一條最優(yōu)的裝配流程使一部汽車從入口開(kāi)始到出口為止的時(shí)間最短。這里，裝配流程是指完成這n步裝配工作的車間序列。請(qǐng)用動(dòng)態(tài)規(guī)劃設(shè)計(jì)一個(gè)O(n)算法來(lái)找到這個(gè)最優(yōu)流程。解：這個(gè)問(wèn)題可以用一個(gè)多級(jí)圖來(lái)描述。圖中起點(diǎn)S代表入口，終點(diǎn)T代表出口。兩點(diǎn)之間有n級(jí)頂點(diǎn)集合，V1，V2，…，Vn，其中Vi(1in)含兩頂點(diǎn)，分別代表A[i]和B[i]。從S到A[1]的邊有權(quán)A[0]，從S到B[1]的邊有權(quán)B[0]，從A[n]到T的邊有權(quán)A[n+1]，從B[n]到T的邊有權(quán)B[n+1]。另外，從Vi(1in-1)的頂點(diǎn)到Vi+1的頂點(diǎn)有4條邊。它們是，邊(A[i],A[i+1])有權(quán)值0，邊(B[i],B[i+1])有權(quán)值0，邊(A[i],B[i+1])有權(quán)值TA[i]，邊(B[i],A[i+1])有權(quán)值TB[i]。另外代表A[i]的頂點(diǎn)有權(quán)值A(chǔ)[i]，代表B[i]的頂點(diǎn)有權(quán)值B[i](1in)。S和T權(quán)值為0。下面的圖給出了一個(gè)n=6的例子。顯然，最優(yōu)流程對(duì)應(yīng)著一條從S到T的最短路徑。與書(shū)中6.5節(jié)中多級(jí)圖不同的是，這里的路徑長(zhǎng)度包括頂點(diǎn)的權(quán)值。圖中粗線標(biāo)出該例子的解。另外，我們定義從入口到每個(gè)車間完成的最佳流程為一個(gè)子問(wèn)題。圖中每個(gè)子問(wèn)題的解標(biāo)在頂點(diǎn)邊上。我們定義子問(wèn)題的解如下：DA[i]=從S到完成A[i]的最短時(shí)間，DB[i]=從S到完成B[i]的最短時(shí)間，(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)。當(dāng)算出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 //準(zhǔn)備輸出路徑，堆棧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)過(guò)的車間endforEnd因?yàn)樗惴ㄖ忻恳粋€(gè)循環(huán)中的每一步只需要O(1)時(shí)間，而每一個(gè)循環(huán)變量最多有n個(gè)不同值，所以算法有O(n)的復(fù)雜度。假設(shè)我們有一個(gè)n個(gè)數(shù)的序列，A[1],A[2],…,A[n]，通過(guò)n-1次對(duì)兩個(gè)相鄰的數(shù)做減法后，序列變成一個(gè)數(shù)。例如，序列4,5,3,9中有4個(gè)數(shù)字。如果我們?cè)?和3之間做減法，因?yàn)?-3=2，序列變?yōu)?,2,9。如果再取4和2做減法，得到序列2,9。最后，在2和9之間做減法，得到一個(gè)數(shù)-7。和矩陣連乘問(wèn)題類似，這個(gè)過(guò)程可以用一個(gè)二叉樹(shù)表示，樹(shù)中每個(gè)內(nèi)結(jié)點(diǎn)代表一個(gè)減法操作。例如，上面的例子可以用下面圖(a)中的二叉樹(shù)表示。讓我們把這樣一棵樹(shù)稱為減法歸約樹(shù)，而每一次減法操作稱為一次減法歸約。顯然，我們可以有許多減法歸約樹(shù)，但我們希望找到一棵最佳減法歸約樹(shù)使最后的數(shù)字最大。不難看出下面圖(b)中的二叉樹(shù)就是上面例子的最佳減法歸約樹(shù)，它產(chǎn)生的最后數(shù)字是11，是最大可能的結(jié)果。5(5(a)序列4,5,3,9的一棵減法歸約樹(shù)(b)序列4,5,3,9的一棵最佳減法歸約樹(shù)94322-79453211-7請(qǐng)?jiān)O(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃的算法為序列A[1..n]找出一棵最佳減法歸約樹(shù)，并分析你的算法的復(fù)雜度。應(yīng)用你的算法算出序列5,-3,7,2,-1的一棵最佳減法歸約樹(shù)。你需要顯示每一步的細(xì)節(jié)。解：(a) 我們把計(jì)算子序列A[i],A[i+1],…,A[j](1ijn)的最佳減法歸約樹(shù)定義為一個(gè)子問(wèn)題。我們定義L(i,j)為子序列A[i],A[i+1],…,A[j]的最佳減法歸約樹(shù)能產(chǎn)生的最大值。當(dāng)i=j時(shí)，L(i,i)=A[i]。為了得到最佳減法歸約樹(shù)，我們需要考慮一個(gè)對(duì)稱的問(wèn)題，即找到一個(gè)減法歸約樹(shù)使得最后的數(shù)值最小。讓我們稱題中的最佳減法歸約樹(shù)為最大歸約樹(shù)，而對(duì)稱問(wèn)題中的最佳減法歸約樹(shù)為最小歸約樹(shù)。讓我們定義S(i,j)是子序列A[i],A[i+1],…,A[j](1ijn)的最小歸約樹(shù)能產(chǎn)生的最小值。當(dāng)i=j時(shí)，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 //子問(wèn)題的規(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這個(gè)算法的復(fù)雜度顯然是O(n3)。下面是由表K和H構(gòu)造最大和最小歸約樹(shù)的遞歸算法。Max-Redude-Tree(L,S,K,H,i,j)ifi=j thenconstructasinglenodepwithvalueA[i] else constructrootnodepwithvalueofL[i,j] //根結(jié)點(diǎn) kK[i,j] left(p)Max-Redude-Tree(L,S,K,H,i,k) //左子樹(shù) right(p)Min-Redude-Tree(L,S,K,H,k+1,j) //右子樹(shù)endifreturnpEndMin-Redude-Tree(L,S,K,H,i,j)ifi=j thenconstructasinglenodepwithvalueA[i] else constructrootnodepwithvalueofS[i,j] //根結(jié)點(diǎn) hS[i,j] left(p)Min-Redude-Tree(L,S,K,H,i,h) //左子樹(shù) right(p)Max-Redude-Tree(L,S,K,H,h+1,j) //右子樹(shù)endifreturnpEnd(b)序列5,-3,7,2,-1的最大歸約樹(shù)的運(yùn)算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最大歸約樹(shù)如下：335-37-1018-132-1*假設(shè)我們有n個(gè)活動(dòng)要申請(qǐng)使用大禮堂:S={a1,a2,…,an}。禮堂從時(shí)間t=0起可以安排。活動(dòng)ai(1i￡n)需要連續(xù)使用的時(shí)間是ti并且在時(shí)刻di前結(jié)束，這里有0<ti￡di<￥。也就是說(shuō)它必須被安排在時(shí)刻di-ti前開(kāi)始，否則不可能按時(shí)完成。因?yàn)樵谌魏螘r(shí)刻，兩個(gè)活動(dòng)不能同時(shí)使用禮堂，所以我們只能滿足一部分活動(dòng)，但我們希望能滿足盡量多的活動(dòng)。請(qǐng)用動(dòng)態(tài)規(guī)劃設(shè)計(jì)一個(gè)O(n2)算法選出集合S中最大的一個(gè)活動(dòng)子集并做出它們可以不沖突地使用大禮堂的調(diào)度，也就是給出每一個(gè)被選中活動(dòng)開(kāi)始的時(shí)刻。(提示：先把集合S中活動(dòng)按他們的結(jié)束時(shí)間di(1i￡n)排序?？杉俣╠1￡d2￡…￡dn。然后，定義子集Si={a1,a2,…,ai}(1￡i￡n)。按照動(dòng)態(tài)規(guī)劃的原理，先考慮S1，再考慮S2，…，最后考慮Sn。為子集Si定義以下子問(wèn)題：能否找出j個(gè)不沖突的活動(dòng)？如果能，最早什么時(shí)刻可完成？我們定義M(i,j)為安排集合Si中j(1￡j￡n)個(gè)不沖突活動(dòng)所需的最短時(shí)間。如果集合Si中不可能找出這j個(gè)活動(dòng)，則置M(i,j)=￥。假設(shè)我們已算出M(i,j)(1￡i￡k-1,1￡j￡n)，我們?cè)撛鯓铀鉓(k,j)(1￡j￡n)?)請(qǐng)用上面的算法找出下面7個(gè)話動(dòng)的最優(yōu)解。A[i]1234567T[i]442.54.5635D[i]587.511.5141215

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