算法第四五章作業(yè)1114s

(1)X：{b,c,e}Y:{b,d,f,c,e}Z:{b,c,d,f,e},,,xr,Y,xr,Y ,ys,Z ,

A X,YZXiX的第ir1s1xrysztxrysztanLCSr1s1

xrysr1sxrysysztxrzt，且anxrLCSXYZr1srs1xrysysztxrzt，且anysLCSXYZrs1rsxrysysztxrztanztLCSXYZrsCi,jkXi,YjZk的最長公共子序列的長度Ci,jk0Xi0或Yj0Zk0Ci,jkCi1,j1k11，當i0,j0xiyjzkCijkmaxCi1,jkCi,j1kCi,jk1，當i0,j0xiyjyjzkxizkC[r,s,t]←[0]B[r,s,t]←emptyFori←1torthenForj←1tosFork←1totIfxi=yj=zkC[i,j,k]←C[i-1,j-1,k-1]+B[i,j,k]←‘-1,-1,-ElseIfC[i-1,j,k]ismaxin{C[i-1,j,k],C[i,j-1,k],C[i,j,k-1]}EndEndforEnd

End

C[i,j,k]←C[i-1,j,B[i,j,k]←‘-1,0,ElseifC[i,j-1,k]ismaxin{C[i-1,j,k],C[i,j-1,k],C[i,j,k-1]}thenC[i,j,k]←C[i,j-1,k]B[i,j,k]←‘0,-1,ElseC[i,j,k]←C[i,j,k-B[i,j,k]←‘0,0,-EndPrint_LCS(B,X,i,j,Ifi=0orj=0ork=0thenreturnIfB[i,j,k]=‘-1,-1,-1’thenPrint_LCS(B,X,i-1,j-1,k-1)PrintX[i]ElseifB[i,j,k]=‘-1,0,0’Print_LCS(B,X,i-1,j,ElseifB[i,j,k]=‘0,-1,0’Print_LCS(B,X,i,j-1,k)ElsethenPrint_LCS(B,X,i,j,k-EndA[i]=max{A[k]}+1;對于任意0<k<i,且voidfor(intfor(int 本題思路與4.4大致相同，采用與4.4A[i]=max{A[k]}+1;對于任意0<k<i,且|A[k]-voidfor(intfor(intif(abs(A[j]-在其他斷點k，此與之前假設(shè)k為最優(yōu)解斷點。所以該問題的優(yōu)化子結(jié)構(gòu)是兩個字串的最優(yōu)解與kn-1sum[i,j]i元素到第jA[i,j]maxA[i,k]A[k1,j]sum[i,j],iikvoidintint sum[i][j]=sum[i][j-for(int for(i=1;i<=n-j=i+len-for(k=i;k<=j-O(n3)voidfor(intdp_max[i][i]=dp_min[i][i]=for(inti=n-1;i>=0;i--for(intdp_max[i][j]=dp_min[i][j]=-for(intintval=if(maxvalue>dp_max[i][j]=if(minvalue<dp_min[i][ij]=算法結(jié)束后，dp_max[1][n]0大值和最小值還要子問題最接近于0的最小正數(shù)以及最接近0的最大負voidinttemp=0,intfor(intintfor(intfor(intfor(int A[i,j]=min{A[i-1,j]+bij,A[i,j- ifA[i,j]=A[i- ifA[i,j]=A[i,j- voidfind_largest for(int for(int for(intfor(int A[i,j]=min{A[i-1,j],A[i,j-1],A[i-1][j-體積為sum/2的情況下，是否存在一種裝法使得背包容納的價值為設(shè)P[i,j]：在可裝物品為1…i號,且背包容量為jw[i]:第iv[i]:i件物品的價值P[i,j]=max{P[i-1,j],P[i-1,j-voidfor(int for(int for(intfor(int P[i,j]=max{P[i-1,j],P[i-1,j-P[n,sum/2]sum/2對所有點按照x坐標從小到大順序排序，分別記為0,1,…,n。設(shè)A[i]表示從0到i的一條路徑，B[j]表示從0到j(luò)的一條路徑。d[i][j]表示為點i與j的直線距離。S[i][j]表示A[i]與B[j]的路徑和的最小長度。代價方程如下： ,i>jS[i][j]=S[i][i]=S[i][i-1]+d[i- , S[i][j]=S[i][j-1]+d[j- for(intfor(intfor(inti=1;i<n- j=i+l-for(intk=i;k<j-q=t[i,k]+t[k+1,j]+w(Δvi-if算法執(zhí)行完畢后從t[1,n]即可求出最優(yōu)三角分割代價分割路徑保存在了

i1,i2,i3…inni2,i3,…in余n-1i2,i3…inT’=[(n-i2，i3…inn-1j2,j3,…jnT<Ti1,j2,j3…jn顯然也是nT’=<=T與i1,i2,…in是n個任務(wù)的最 ，因此，i2,i3…in是子問剩余n-1n<-createnewarrayA[1:n]Fori<-1tonDoForj<-1tonDoifThenmin<-returnO（1，3-復(fù)雜度為O（1O(n2).n>=101角硬幣，最優(yōu)解為x51x’>=x+15<=n<1052<=n<52n<21mn-m<=n-m題有一個更優(yōu)的解使硬幣的的個數(shù)x‘-1<x-1,那么加上選擇的第一個硬幣，不等式即可化為x’<x，與原問題的解是最優(yōu)，因此該問題具有優(yōu)化子結(jié)Input:nX<-Return（sa<=（sb（s1<=L(s2).（sa>=（s1（sbTTcost（T）=-L(sa)dt(sa)+L(s1)dt(s1)-L(sa)dt’(sa)-=L(sa)dt(sa)+L(s1)dt(s1)-L(sa)dt(s1)-=(L(sa)-L(s1))(dt(sa)-由于L（sa）>=L(s1),dt(sa)>=dt(s1),因此cost（T）-cos（T>cost(T（T）>=cost（T）.cost（T）<=cost(Tcost(T)=cost（T）,T（2）TS={si|0<=i<=ksxsyT意兩個相鄰的葉節(jié)點，szsz（sy）的字符，T’=T-{sx,sy}S’=S-{sx,sy}szcost（T）=cost（T）+L(sx)+L(sy)-1.{sxsy}dt（v=dt（vL（svd（sv=L（svdt（svdt（sx）=dt（sy）=dt（sz）+1，則有1=（L（sx）+L(sy)（dt’(sz)+1）-=(L(sx)+L(sy))dt’(sz)+L(sx)+L(sy)-=L(sz)dt’(sz)+L(sx)+L(sy)-Tcost（T）<cost（T）.TT的子節(jié)點，則得到了STCost(T)=cost(T)+L(sx)+L(sy)-T是優(yōu)化解，故T’是S’的優(yōu)化解樹。（1）算法偽代碼：Input：kS[1:k]Q<-fori<-1ton-doz<-Allocat-x<-left[z]<-Extract-MIN(Q)z<-Merge(x,y)cost<-cost+length(x)+length(y)-1returnOutput:編碼樹Merge(T1,ifT1=emptythenreturnT2ifT2=emptythenreturnT1T←newRootT.left←Merge(T1.left,T2.left)T.right←Merge(T1.right,T2.right)ReturnTTree(C,s,Mid←(s+e)/Returnmerge(Tree(C,s,mid),Tree(C,mid+1,貪心思想：為了得到代價最大的映射，每次選擇A，Baibif（ai）=bi，這樣獲得的代價將最大。Output:A到B的映射fMax—n<-createnewarrayf[1:n][1:2]fori<-1tondof[i][1]<-f[i][2]<-return1-2O(1)，3-4O（1時間復(fù)雜度為T（n）=O（nlognf(a1)=b1,f(ai)=bj.C’=a1^b1+ai^bj+Cr.映射f：f(ai)=bi,1<=i<=n=bi,2<=i<=n是子問題A-a1和B-b1的優(yōu)化解若不然存在一個更優(yōu)的映射f與f是原問題的優(yōu) （1）I={[p1,q1],…[pm,qm]}q1<q2<…qmInput：排序后區(qū)間[p1,q1]…[pm,qm]IP，和Q.Output：S。n<-S<-j<-fori<-2todoifthenS<-j<-return存在一個I’的相容區(qū)間問題的優(yōu)化解B|B’|>A’,B={1}B’,iI，pi>q1,B|+1,|B|=|B’|+1>|A’|+1=|A|,與A最大相，因此該問題具有優(yōu)化子結(jié)構(gòu)pi/wiInput:C,W,V,NOutput:XX←V/WNFori1tolength(N)thenIfC≥W[N[i]]thenX[N[i]]←C←C-ElseifX[N[i]]←En