中國科學院大學計算機學院計算機算法劉玉貴期末題庫習題答案-第五章動態(tài)規(guī)劃練習參考答案

第五章動態(tài)規(guī)劃練習參考答案一、習題五1．解：1)第一層for循環(huán)n，內(nèi)層循環(huán)n,n-1,…1,所以T(n)=1=2+…+n=n(n-1)/2=O(n2)2)分治算法：和最鄰近點對的算法類似，我們可以在k=n/2的位置將A=<a1,a2,…an>劃分為A1和A2兩半，于是A的最大子段和可能是三種情況：出現(xiàn)在A1部分、出現(xiàn)在A2部分、出現(xiàn)在橫跨兩邊的中間部分。前兩種情況恰好對應(yīng)兩個規(guī)模減半的子問題，第三種情況,設(shè)最大子段為[p..q]，則一定p≤k,q≥k+1，只需從A[k]和A[k+1]分別向前和向后求和，記下其最大的和S1,S2，則S1+S2就是橫跨中心的最大和。算法如下：MaxSubSum(A,left,right){輸入：數(shù)組A,left、right分別是A的左右邊界；輸出：A的最長子段和sum及子段的前后邊界。ifleft=rightthenreturnmax(A[left],0)k:=(left+right)/2leftsum:=MaxSubSum(A,left,k)Rightsum:=MaxSubSum(A,k+1,right)S1:=A1[k]//從k向左的最大和,參考1)內(nèi)循環(huán)改為forj=kto1S2:=A2[k+1]//從k向右的最大和,求s1,s2需掃描整個數(shù)組O(n)Sum:=s1+s2Ifleftsum>sumthensum:=leftsumIfrightsum>sumthensum:=rightsum}算法復雜度：T(n)=2T(n/2)+O(n)=O(nlogn)(主定理之情形2)3)這個問題如何確定子問題是個有意思的事情，需要認真考慮。如我們可能很自然設(shè)C[i]=A[1..i]的最大和，但它不滿足最優(yōu)子結(jié)構(gòu)。因為使A[1..i]達到最大和的子段未必包含A[i]，計算后面的問題不能直接把該子段直接組合進來。如A=<2,-5,8,1,-9,4,6>，C[5]=8+1=9，在計算C[6]時不能把<8,1>直接組合進來，因為后面有-9，對連續(xù)和也有影響。例中，C[7]=4+6，C[6]顯然不是4，而是8+1。所以這樣定義的C不滿足最優(yōu)子結(jié)構(gòu)。按提示，定義b(j)=為輸入A[1..j]中必須包含A[j]的最大子段和，b[j]滿足最優(yōu)子結(jié)構(gòu)性質(zhì)：若b[j+1]最大，則b[j]必然最大，從b[j+1]=得b[j+1]=b[j]+A[j+1]即可很易證明。據(jù)此可得遞推公式：b[j]=max{b[j-1]+A[j],A[j]},j=1,2,..n；b[0]=0.這里還有一個問題：b[j]并不是A[1..j]的最大子段和，只是包含A[j]的最大子段和。但我們已得到b[1],b[2],…b[n]，恰好枚舉了以任何元素為最后元素的的所有子段的最大和，A[1..n]的最大子段和一定在其中：對n個和比較取最大者即可。算法描述：MaxSum(A,n){輸入：數(shù)組A；輸出：組大字段和sum，子段的最后位置cSum:=0b:=0fori:=1tondoifb>0thenb:=b+A[i]elseb:=A[i]endififb>sumthensum:=bc:=iendifend{for}returnsum,c}尚有一點工作：從sum，c找到子段的左邊界(略)。算法復雜度：顯然T(n)=O(n)。注意:很多同學,使用,tai=max(ta+a(i),tb),tbi=max(ta,tb+b(i)),即對第i個任務(wù)以誰加工總長最短來安排，ifTai<TbiA加工elseB加工這是貪心算法，不正確，第10章有多機調(diào)度近似算法、反例。又如反例：n=3，(a1,a2,a3)=(2,5,6)，(b1,b2,b3)=(3,6,3),貪心調(diào)度為A1B2A3，max=8；更優(yōu)A1A2B3,max=7。2.解：在完成前k個作業(yè)時，設(shè)機器A工作了x時間，則機器B此時最小的工作時間是x的一個函數(shù)。設(shè)F[k][x]表示完成前k個作業(yè)時，機器B最小的工作時間，則F[k][x]=min{F[k-1][x]+bk,F[k-1][x-ak]}其中F[k-1][x]+bk對應(yīng)第k個作業(yè)由機器B來處理（完成k-1個作業(yè)時機器A的工作時間仍是x，則B在k-1階段用時F[k-1][x]；而F[k-1][x-ak]對應(yīng)第k個作業(yè)由機器A處理（完成k-1個作業(yè)，機器A工作時間是x-a[k]，而B完成k階段與完成k-1階段用時相同為F[k-1][x-ak]。則完成前k個作業(yè)所需的時間為：max{x,F[k][x]}。根據(jù)遞推關(guān)系，很容易證明問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。解為：min(max(x,f(N,x)),0<=x<=a(i)。當處理第一個作業(yè)時，a[1]=2,b[1]=3;機器A所花費時間的所有可能值范圍：0≤x≤a[0].x<0時，設(shè)F[0][x]=∞，則max(x,∞)=∞；0≤x<2時，F(xiàn)[1][x]=3，則Max(0,3)=3，x≥2時，F(xiàn)[1][x]=0，則Max(2,0)=2；2）處理第二個作業(yè)時：x的取值范圍是：0<=x<=(a[0]+a[1])，當x<0時，記F[2][x]=∞；以此類推下去(略)。3.解：這是整數(shù)背包問題。類似0/1背包問題，易證滿足最優(yōu)子結(jié)構(gòu)性質(zhì)：設(shè)y1,y2,..,yn是原問題的最優(yōu)解，則y1,y2,..,yn-1是下述子問題：,S.T.,xi∈{0,1,2},1≦i≤n-1的最優(yōu)解。如不然，y/1,y/2,…,y/n-1是子問題的最優(yōu)解，則,則，y/1,y/2,…,y/n-1,yn將是原問題的可行解解，且，與y1,y2,…,yn是最優(yōu)解矛盾。遞推公式：設(shè)m[k][x]表示容量約束x，可裝入1,2,…k件物品的最優(yōu)解，則m[k][x]=max{m[k-1][x],m[k-1][x-ak]+ck,m[k-1][x-2ak]+2ck},0≤x≤bm[0][x]=0,ifx>=0;m[0][x]=-∞,ifx<0;m[k][<0]=-∞,k=1,2,..n據(jù)此不難給出算法的描述。（略。仿照0/1背包問題，但那個程序是從后向前推的，上述遞推是從前往后。本問題可以擴展到xi可以取值0,1,2，…m,，遞推部分改為m[k][x]=max{m[k-1][x-xiak]+xick}，對0≤xi≤m取max即可）4.解：問題可描述為：,s.t.。下面證明問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。設(shè)m1,m2,…mn-1,mn是原問題的最優(yōu)解，則其可靠性為，那么不難證明m1,m2,…mn-1是下述問題的最優(yōu)解：(仿照上述3：如果不是，存在…..略)。，s.t.。遞推關(guān)系：設(shè)M[k][x]為成本x，前k級設(shè)備串聯(lián)所得最優(yōu)可靠性值，則m[k][x]=max{m[k-1][x-mkck]×gk(mk)}，1≤mk≤x/ckm[0][x]=1，x>=0;m[k][ck]=1。算法描述：Safe(c[],g[],C){//g[i]()是函數(shù)gi()Intm[][],p[][]C=c-c(i)//每級至少一個設(shè)備for(j=0toC)m[0][j]=1for(i=1ton){forj=0toc{m[i][j]=0for(k=0toj/c[i]){t=m[i-1][j-k*c[i]]g[i](k)ifm[i][j]<tthen{m[i][j]=tp[i][j]=k//此處可用p[i][j]記錄k=mi}}}最優(yōu)解是m[n][C]?；厮萸髆i：p[n][C]=mn;C=C-mn*c[n];P[n-1][C]=mn-1；…..（注：由于c(i)可能是實數(shù)，上述算法是示意，用類似0/1背包問題數(shù)對的遞推方式可能更具一般性）二、1.解：使用動態(tài)規(guī)劃設(shè)計技術(shù)。對于i=1,2,…n，考慮以xi為最后項的最長遞增子序列的長度C[i]。如果在xi前存在xj<xi，則C[i]=max{C[j]}+1,；否則C[j]=1。顯然，若C[i]的子序列是i1i2…iki，則C[ik]的子序列是i1i2…ik，滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。因此C[1]=1，對i>1，C[i]=C[i]=max{C[j]}+1,存在j,1<=j<I,xj<xi；或C[i]=1，任給j，1<=j<I,xj>xi；所求最長子序列的長度是C=max{C[i]|i=1,2…n}。算法設(shè)計時用K[i]記錄C[i]最大時的j，C[i]=1時，K[i]=0；則從K[]可追蹤出解序列：K[i],K[K[i]]….。算法描述略，參考習題五、1,3）。算法復雜度：對每個i需要檢索比i小的所有j，需O(n)時間，i取值n種，所以T(n)=O(n2)。對于給定的實例A=<2,8,4,-4,5,9,11>，計算過程如下：C[1]=1，K[1]=0C[2]=max{C[1]+1)=2，K[2]=1C[3]=max{C[1]+1}=2，K[3]=1C[4]=1,K[4]=0C[5]=max{C[1]+1,C[3]+1,C[4]+1}=3，K[5]=3C[6]=max{C[1]+1,C[2]+1,C[3]+1,C[4]+1,C[5]+1}=4，K[6]=5C[7]=max{C[1]+1,C[2]+1,C[3]+1,C[4]+1,C[5]+1,C[6]+1}=5，K[7]=6C[7]=5是最大值。子序列追蹤過程：11，A[K[7]]=A[6]=9,A[K[6]]=A[5]=5,A[K[5]]=A[3]=4,A[K[3]]=A[1]=2，得解為<2,4,5,9,11>。注：本題可以有多解。2．解：與0/1背包問題類似，使用動態(tài)規(guī)劃算法。令N(j,d)表示考慮作業(yè)集{1,2,…,j}、結(jié)束時間剩余d的最優(yōu)調(diào)度的效益，那么N(j,d)=max{N(j-1,d),N(j-1,d-t(j)+v(j)},d≥t(j);N(j,d)=N(j-1,d),d<t(j)初值：N(1,d)=v(1)，t(1)≤d；N(1,d)=0,t(1)>dN(j,0)=0;N(j,d)=-∞,d<0自底向上計算，用B(j,d)記錄N(j,d)達到最大時是否N(j-1,d-t(j))=v(j)>N(j-1,d)，如果是，B(j,d)=j，否則，B(j,d)=B(j-1)。算法描述：輸入：加工時間t[1..n]，效益v[1..n]，結(jié)束時間D輸出：最優(yōu)效益N[i,j]，標記函數(shù)B[i,j]，i=1.2..n,j=1,2,..D。ford:=1tot[1]-1N[1,d]:=0;B[1][d]:=0Ford:=t[1]toDN[1,d]:=v[1];B[1][d]=1Forj:=2ton{Ford:=1toD{N[j,d]:=N[j-1,d]B[j,d]:=B[j-1,d]Ifd>t[j]andN[j-1,d-t[j]]+v[j]>N[j-1,d]then{N[j,d]:=N[j-1,d-t[j]]+v[j]B[j,d]:=j}}(ford)}(foj)得到最大效益N[n,D]后，通過對B[n,D]的追蹤，可以得到問題的解。算法的主要工作是j、d循環(huán)，需執(zhí)行O(nD)次，循環(huán)體內(nèi)關(guān)鍵操作是常數(shù)，所以T(n)=O(nD)。3.解：如圖所示，n邊形的頂點是1,2,..,n，頂點i-1,i,…j構(gòu)成的凸多邊形記做A[i,j]，于是原始問題就是A[2,n]。考慮子問題A[i,j]的劃分。假設(shè)它的所有劃分方案中的最小權(quán)值是t[i,j]，從i,i+1,…,j-1中任選點k，它與底邊(i-1)j構(gòu)成一個三角形，如圖中灰色三角形所示。這個三角形將A[i,j]劃分為兩個凸多變形：A[i,k]和A[k+1,j]，從而產(chǎn)生了兩個子問題。這兩個凸多邊形的劃分方案的最小權(quán)值分別是t[i,k]和t[k+1,j]。根據(jù)動態(tài)規(guī)劃的思想，A[i,j]相對于這個k的劃分方案的最小權(quán)值是：t[i,k]+t[k+1,j]+d(i-1)k+dkj+d(i-1)j其中d(i-1)k+