算法設計與分析：第7章 動態(tài)規(guī)劃法

第7章動態(tài)規(guī)劃法

學習要點：理解動態(tài)規(guī)劃算法的概念。掌握動態(tài)規(guī)劃算法的基本要素 （1）最優(yōu)子結構性質 （2）重疊子問題性質掌握設計動態(tài)規(guī)劃算法的步驟。理解動態(tài)規(guī)劃算法與分治法、貪心法的異同通過應用范例學習動態(tài)規(guī)劃算法設計策略。 （1）多段圖問題、、關鍵路徑問題 （2）每對結點間的最短路徑 （3）最長公共子序列 （4）0/1背包章節(jié)內容

7.1一般方法和基本要素

7.2每對結點間的最短路徑

7.4最長公共子序列

7.60/1背包7.1一般方法和基本要素動態(tài)規(guī)劃算法總體思想動態(tài)規(guī)劃算法的基本要素設計動態(tài)規(guī)劃算法的步驟動態(tài)規(guī)劃法與分治法、貪心法的區(qū)別動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題動態(tài)規(guī)劃算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=但是經分解得到的子問題往往不是互相獨立的。不同子問題的數目常常只有多項式量級。在用分治法求解時，有些子問題被重復計算了許多次。動態(tài)規(guī)劃算法總體思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。動態(tài)規(guī)劃算法總體思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)

動態(tài)規(guī)劃算法的基本要素（1）最優(yōu)子結構性質——用動態(tài)規(guī)劃法求解的前提。

當一個問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結構性質。一個問題的活動過程可以分為若干個階段，每個階段可包含一個或多個狀態(tài)，從初始階段的初始狀態(tài)出發(fā)做出每個階段的決策，形成一個決策序列。利用問題的最優(yōu)子結構性質，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構造出整個問題的最優(yōu)解。

動態(tài)規(guī)劃算法的基本要素（2）子問題重疊性質 （遞歸算法求解問題時）每次產生的子問題并不總是新問題，有些子問題被反復計算多次，這種性質稱為子問題重疊性質。動態(tài)規(guī)劃算法對每一個子問題只解一次，而后將其解保存在一個表格（通常用二維數組）中，當再次需要解此子問題時，只是簡單地用常數時間查看一下結果。通常不同的子問題個數隨問題的大小呈多項式增長。因此用動態(tài)規(guī)劃算法只需要多項式級時間，從而獲得較高的解題效率。設計動態(tài)規(guī)劃算法的步驟

用動態(tài)規(guī)劃算法求解問題的步驟：1、找出最優(yōu)解的性質，并刻劃其結構特征；2、遞歸地定義最優(yōu)解值；3、自底向上求最優(yōu)解值；4、根據計算最優(yōu)解值時得到的信息構造一個最優(yōu)解（此步只在要求得到最優(yōu)解時才需要做）。動態(tài)規(guī)劃法是一種求解最優(yōu)化問題的重要算法策略。

由動態(tài)規(guī)劃法求解的兩大要素：利用最優(yōu)子結構性質及所獲得的遞推關系式（較小子問題最優(yōu)解與較大子問題最優(yōu)解之間存在的數值關系）去求取最優(yōu)解，可以使計算量較之窮舉法急劇減少。動態(tài)規(guī)劃法的子問題往往是重疊的。如果采用與分治法類似的直接遞歸方法求解將十分費時。為了避免重復計算，動態(tài)規(guī)劃算法一般采用自底向上方式進行計算，并保存已經求解的子問題的最優(yōu)解值。動態(tài)規(guī)劃法與分治法共同點： 將待求解的問題分解成若干子問題，先求解子問題，然后再從這些子問題的解得到原問題的解。不同點：1、適合于用動態(tài)規(guī)劃法求解的問題，分解得到的各子問題往往不是相互獨立的； 而分治法中子問題相互獨立。2、動態(tài)規(guī)劃法用表保存已求解過的子問題的解，再次碰到同樣的子問題時不必重新求解，而只需查詢答案，故可獲得多項式級時間復雜度，效率較高； 而分治法中對于每次出現的子問題均求解，導致同樣的子問題被反復求解，故產生指數增長的時間復雜度，效率較低。共同點： 都是求解最優(yōu)化問題；都具有最優(yōu)子結構性質。不同點：1、求解方式不同：

動態(tài)規(guī)劃法：自底向上；

貪心法：自頂向下。以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題。2、對子問題的依賴不同：

動態(tài)規(guī)劃法：依賴于各子問題的解。只有在解出相關子問題后,才能作出選擇；應使各子問題最優(yōu)，才能保證整體最優(yōu)；

貪心法：不依賴于子問題的解。僅在當前狀態(tài)下作出最好選擇，即局部最優(yōu)選擇。

動態(tài)規(guī)劃法與貪心法多段圖問題

一種特殊的有向無環(huán)圖的最短路徑問題。 （例7-1）帶權有向圖G=(V,E)中的結點被劃分成k個互不相交的子集Vi

(1≤i≤k)

。其中：V1只包含源點s，Vk只包含匯點t；圖中的邊<u,v>均滿足：若uVi則vVi+1。 求從s到t的一條長度最短的路徑（P137圖7-1）。由每個階段所作出的決策組成的決策序列，產生一條從s到t的路徑——多段圖問題的一個可行解。目標函數（每條路徑上所有邊的權值之和，即路徑長度）最小的一條路徑為最優(yōu)解，該路徑長度為最優(yōu)解值。多段圖的最優(yōu)子結構證明

假設(s,v2,v3,...,vk-1,t)是一條從s到t的最短路徑，并假定由源點s經過初始決策已經到達狀態(tài)v2

。則將v2看成某個子問題的初始狀態(tài)，該子問題尋找一條從v2到t的最短路徑。

證明（多段圖具有最優(yōu)子結構性質）如果(s,v2,v3,...,vk-1,t)是一條從s到t的最短路徑，則(v2,v3,...,vk-1,t)必是一條從v2到t的最短路徑。（反證）假如(v2,v3,...,vk-1,t)不是從v2到t的最短路徑，另有(v2,q3,...,qk-1,t)是從v2到t的最短路徑，那么路徑(s,v2,q3,...,qk-1,t)顯然比(s,v2,v3,...,vk-1,t)更短。 與假設矛盾！多段圖的最優(yōu)子結構性質得證！在分析（證明）問題的最優(yōu)子結構性質時，所用的方法具有普遍性：首先假設由問題的最優(yōu)解導出的子問題的解不是最優(yōu)的，然后再設法說明在這個假設下可構造出比原問題最優(yōu)解更好的解，從而導致矛盾。多段圖問題的遞推式（向前遞推）

由多段圖問題的最優(yōu)子結構性質，容易得到多段圖問題的遞推式，從而由子問題的最優(yōu)解來計算原問題的最優(yōu)解： 多段圖問題的向前遞推式：（式7-1）cost(i,j)是從第i階段中的結點j，到匯點t的最短路徑長度。cost(i+1,p)是從后繼結點（第i+1階段中的結點）p到匯點t的最短路徑長度。（子問題的最優(yōu)解）c(j,p)+cost(i+1,p)是從第i階段結點j，經過第i+1階段結點p到達匯點t的路徑長度。cost(i,j)則是這些路徑中的最短路徑長度。<j,p>E表示j,p之間有邊01234567891011源點st匯點97321242711118654356524v1v2v3v4v5階段使用式（7-1）向前遞推式，由后向前計算最優(yōu)解值—cost(1,0)cost(5,11)=0,cost(4,10)=5,cost(4,9)=2,cost(4,8)=4,cost(3,7)=min{6+cost(4,10),5+cost(4,9)}=7,cost(3,6)=...=5,cost(3,5)=...=7,cost(2,4)=min{8+cost(3,7),11+cost(3,6)}=15,cost(2,3)=18,cost(2,2)=...=9,cost(2,1)=...=7,

cost(1,0)=min{9+cost(2,1),7+cost(2,2),3+cost(2,3),2+cost(2,4)}=1601234567891011源點st匯點97321242711118654356524v1v2v3v4v5階段若想求最優(yōu)解，必須在計算最優(yōu)解值的過程中保存一些必要信息?？捎胐(i,j)來記錄從第i階段結點j到匯點t的最短路徑上該結點的下一個結點編號。根據前面例7-1求最優(yōu)解值cost(1,0)的過程中，產生的中間結果：cost(5,11)=0,cost(4,10)=5,cost(4,9)=2,cost(4,8)=4,cost(3,7)=min{6+cost(4,10),5+cost(4,9)}=7,cost(3,6)=...=5,cost(3,5)=...=7,cost(2,4)=min{8+cost(3,7),11+cost(3,6)}=15,cost(2,3)=18,cost(2,2)=...=9,cost(2,1)=...=7,cost(1,0)=min{9+cost(2,1),7+cost(2,2),3+cost(2,3),2+cost(2,4)}=16可知：d(4,10)=d(4,9)=d(4,8)=11, d(3,7)=d(3,6)=d(3,5)=9, d(2,4)=d(2,3)=7, d(2,2)=5, d(2,1)=6, d(1,0)=1或2很容易從d的值確定最短路徑上的結點，得到兩條最短路徑：(0,d(1,0)=1,d(2,1)=6,d(3,6)=9,d(4,9)=11)和(0,d(1,0)=2,d(2,2)=5,d(3,5)=9,d(4,9)=11)多段圖顯然具有重疊子問題性質：計算cost(3,7)、cost(3,6)、cost(3,5)時都要用到cost(4,9)的值，因此保存cost(4,9)的值可以避免重復計算。程序7-1：多段圖的向前遞推動態(tài)規(guī)劃算法FMultiGraph(intk,int*p) //共k個階段，n個結點{//帶權有向圖G（多段圖）采用鄰接表存儲（見程序6-8）

float*cost=newfloat[n];//一維數組cost[j]保存結點j到匯點t的最短路徑

int*d=newint[n];//一維數組d[j]保存cost[j]對應的最短路徑上的下一個結點

cost[n-1]=0；d[n-1]=-1;//設置向前遞推的初值(最大結點編號為n-1)

for(intj=n-2;j>=0;j--)

//按結點編號n-2,...,0的順序計算cost[j]和d[j]{ floatmin=INFTY;//min求得的最小值，即為當前結點j的cost[j] for(ENode<T>*r=a[j];r;r=r->nextArc)//用指針r遍歷鄰接表中a[j]的鄰接結點

{ intv=r->adjVex; //當前階段的結點j與下一階段的結點v之間有邊

if(r->w+cost[v]<min) {min=r->w+cost[v];q=v;} }

cost[j]=min;d[j]=q;//q是最短子路徑上j的下一個結點編號

}

c=cost[0]; p[0]=0; //c保存的是最優(yōu)解值,p[0]是源點0

for(j=1;j<=k-1;j++)

p[j]=d[p[j-1]];//數組p[]保存最優(yōu)解，p[i]是最短路徑上第i階段結點}前提：結點已按拓撲順序排序。思考：如何得到？程序7-1：多段圖的向前遞推動態(tài)規(guī)劃算法FMultiGraph(intk,int*p) //共k個階段，n個結點{//帶權有向圖G（多段圖）采用鄰接表存儲（見程序6-8）

float*cost=newfloat[n];//一維數組cost[j]保存結點j到匯點t的最短路徑

int*d=newint[n];//一維數組d[j]保存cost[j]對應的最短路徑上的下一個結點

cost[n-1]=0；d[n-1]=-1;//設置向前遞推的初值(最大結點編號為n-1)

for(intj=n-2;j>=0;j--)

//按結點編號n-2,...,0的順序計算cost[j]和d[j]{ floatmin=INFTY;//min求得的最小值，即為當前結點j的cost[j] for(ENode<T>*r=a[j];r;r=r->nextArc)//用指針r遍歷鄰接表中a[j]的鄰接結點

{ intv=r->adjVex; //當前階段的結點j與下一階段的結點v之間有邊

if(r->w+cost[v]<min) {min=r->w+cost[v];q=v;} }

cost[j]=min;d[j]=q;//q是最短子路徑上j的下一個結點編號

}

c=cost[0]; p[0]=0; //c保存的是最優(yōu)解值,p[0]是源點0

for(j=1;j<=k-1;j++)

p[j]=d[p[j-1]];//數組p[]保存最優(yōu)解，p[i]是最短路徑上第i階段結點}思考：若結點順序打亂又該怎么辦？僅能得到一條最短路徑。多段圖問題的遞推式（向后遞推）多段圖問題也可用向后遞推式（式7-2）來解決：Bcost(i,j)表示從源點s到第i階段狀態(tài)j的最短路徑長度。Bcost(i-1,p)是從源點到前繼結點（第i-1階段中的結點）p的最短路徑長度。（子問題的最優(yōu)解）c(p,j)+Bcost(i-1,p)是從源點，經過第i-1階段結點p，到達第i階段結點j的路徑長度。Bcost(i,j)則是這些路徑中的最短路徑長度。向后遞推動態(tài)規(guī)劃法的實現，請課后自行完成！多段圖問題的應用——資源分配問題（例7-2）將n個資源分配給r個項目，求總收益最大的資源分配方案。若將j個資源分配給第i個項目，可以收益N(i,j),1≤i≤r,0≤j≤n。每個狀態(tài)V(i,j)代表前i-1個項目已經分配了j個資源；邊<V(i,j),V(i+1,k)>上的權值代表本次分配N(i,k-j)的收益。可得如下多段圖(將4個資源分配給3個項目)：0s=V(1,0)r=V(4,4)N(1,0)N(1,1)V(2,0)v1v2v3v4階段N(1,2)N(1,4)N(1,3)V(2,1)V(2,2)V(2,3)V(2,4)V(3,0)V(3,1)V(3,2)V(3,3)V(3,4)N(2,0)N(2,1)N(2,0)N(2,1)N(2,0)N(3,0)max{N(3,0),N(3,1)}max{N(3,0),N(3,1),N(3,2)}雖然一般來說，分配的資源數目越多應該收益越大，但并非完全如此。因此，圖中最后兩個階段間的邊<V(r-1,j),V(r,n)>的權值取即：不一定要將n個資源全部分配完，才能獲得最大收益。

此問題的向后遞推動態(tài)規(guī)劃算法可自行編寫。多段圖問題的應用

——關鍵路徑問題

關鍵路徑法是利用AOE網絡進行工程安排的一種方法,求一個帶權有向無環(huán)圖中兩結點間的最長路徑. AOE網絡是一個帶權有向圖G=(V,E),它以結點代表事件(event)，有向邊代表活動(activity)。有向邊的權代表：活動持續(xù)時間(duration).結點代表的事件代表：入邊代表的活動已經完成,出邊代表的活動可以開始.完成工程所需的最短時間是AOE網中從開始結點到完成結點的最長路徑的長度.這條最長路徑稱為關鍵路徑，路徑上的邊稱為關鍵活動.(關鍵活動對整個工程的最短工期有影響,如果不能按時完成會影響整個工程的進度.) (例7-3)如下圖是AOE網絡的一個例子,代表有11項活動和9個事件的工程.(其中源點0表示整個工程開始,匯點8代表整個工程結束.)01236456451127898424(1)事件i可能的最早發(fā)生時間earliest(i):指從開始結點s到結點i的最長路徑(關鍵路徑)長度;(2)事件i允許的最遲發(fā)生時間latest(i):指在不影響工期的條件下,事件(結點)i允許的最晚發(fā)生時間;等于earliest(n-1)減去從結點i到結點n-1的最長路徑長度.(3)關鍵活動:若latest(j)-earliest(i)=w(i,j),則邊<i,j>代表的活動是關鍵活動.關鍵活動組成的關鍵路徑上每個結點(i和j)都有l(wèi)atest(i)=earlist(i).關鍵路徑問題具有最優(yōu)子結構和重疊子問題這兩個基本要素,因此可以用動態(tài)規(guī)劃法求解(見P141)。關鍵路徑算法的基本步驟:

若AOE網絡中的結點已經按拓撲序列的次序編號,則(1)對帶權有向圖G進行拓撲排序,確認其是否為無環(huán)圖;(2)按拓撲次序計算earliest[i],0≤i≤n-1;(3)按逆拓撲次序計算latest[i],0≤i≤n-1;(4)對每一條邊<i,j>計算latest[j]-earliest[i],并檢查latest[j]-earliest[i]是否等于w[i][j],w[i][j]是邊<i,j>的權,從而確定關鍵活動(邊).從前向后遞推求earliest(j):

最終求得的earliest(n-1)就是關鍵路徑(最長路徑)的長度.從后向前遞推求latest(i):0123645645112789842401236456451127898424例7-3AOE網絡的關鍵路徑計算結果見下表:012345678earliest(i)064577161519latest(i)0669711171519對每條邊<i,j>所代表的活動計算latest(j)-earliest(i)的值,如果等于邊的權值w(i,j),則該活動為關鍵活動.

如:<0,1>,<1,4>,<4,7>,<7,8>就是關鍵活動.由關鍵活動組成的關鍵路徑為(0,1,4,7,8),長度為19.關鍵路徑上的所有結點i滿足earliest(i)=latest(i)。以鄰接表作存儲結構；從源點V0出發(fā)，令earliest[0]=0,按拓撲序列求各頂點的earliest[i]；從匯點Vn-1出發(fā)，令latest[n-1]=earliest[n-1],按逆拓撲序列求其余各頂點的latest[i]；若每條弧ak關聯的邊為<vi,vj>，根據各頂點的earliest和latest值，計算每條弧的early[k]=earliest(i)和late[k]=latest(j)-w(i,j),找出early[k]=late[k]的關鍵活動。算法實現template<classT>voidExtLGraph<T>::Earliest(int*earliest,int*order)//求各頂點的earliest[i]{for(inti=0;i<n;i++)earliest[i]=0;for(i=0;i<n;i++) //從前向后{

//前提：圖的拓撲排序結果已存在于order數組中

intk=order[i];for(ENode<T>*p=a[k];p;p=p->nextArc)if(earliest[p->adjVex]<earliest[k]+p->w)

earliest[p->adjVex]=earliest[k]+p->w;

//更新k的所有后繼結點的earliest[]值}}template<classT>voidExtLGraph<T>::Latest(int*latest,int*order,intlongest)//求各頂點的latest[i]{ for(inti=0;i<n;i++)latest[i]=longest;for(i=n-2;i>-1;i--) //從后向前

{

//圖的拓撲排序結果已存在于order數組中

intj=order[i];

for(ENode<T>*p=a[j];p;p=p->nextArc) if(latest[j]>latest[p->adjVex]-p->w)

latest[j]=latest[p->adjVex]-p->w;

//更新j的latest[]值

}}

性能分析關鍵路徑算法與拓撲排序有相同的時間復雜度，其時間復雜度為O(n+e)。課堂練習：求下圖中的關鍵路徑和關鍵活動8765342105413322634142012345678earliest(i)025457111014latest(i)036457111014<0,3>,<3,4>,<3,5>,<4,6>,<5,7>,<6,8>,<7,8>是關鍵活動.因此關鍵路徑有(0,3,4,6,8)和(0,3,5,7,8),

長度為14.7.2每對結點間的最短路徑弗洛伊德(Floyd)算法—求帶權有向圖G=(V,E)中任意一對結點間的最短路徑。允許有向圖包含負邊，但不允許圖中包含路徑長度為負值的回路。(圖7-4)該最短路徑問題可證明具有最優(yōu)子結構特性和重疊子問題性質（參見P143-1447.2.2），因此可用動態(tài)規(guī)劃算法求解。最優(yōu)解（兩結點間最短路徑）的遞推關系為：

d-1[i][j]代表從i到j的路徑上不包含任意其他結點時的長度。（w[i][j]的定義見式7-5)dk[i][j]是：從結點i到結點j的路徑上，只允許包含結點編號不大于k的結點時，所有可能路徑中的最短路徑長度。則dn-1[i][j]=(i,j)。程序7-2弗洛伊德算法解兩結點間最短路徑問題voidFloyd(T**d,int**path){ //有向圖存儲在鄰接矩陣a中//二維數組元素d[i][j]存放從結點i到結點j的最短路徑長度。//二維數組元素path[i][j]記錄結點i到結點j的最短路徑上結點j的前一結點。

for(k=0;k<n;k++) //以k作為中間結點

for(i=0;i<n;i++) for(j=0;j<n;j++) if(d[i][k]+d[k][j]<d[i][j])

//用第k列和第k行的元素，更新其它所有元素d[i][j] { d[i][j]=d[i][k]+d[k][j]; path[i][j]=path[k][j]; }}容易看出弗洛伊德算法的時間復雜度為O(n3)弗洛伊德算法的正確性證明定理7-1：弗洛伊德算法得到的d[i][j](0≤i,j≤n-1)是從i到j的最短路徑。證明：（歸納法）初始時d[i][j]=w[i][j]，從i到j路徑上沒有其他結點，因此正確。歸納假設：在k次循環(huán)后算法正確，d[i][j]（即dk-1[i][j])為從i到j的路徑上不含編號從k到n-1的結點時的最短路徑長度。第k+1次循環(huán)中執(zhí)行：若d[i][k]+d[k][j]<d[i][j]（即dk-1[i][j]

）時，d[i][j]更新為d[i][k]+d[k][j]（即dk[i][j]

）。 因為由最優(yōu)子結構性質：若i到j的最短路徑經過k，則必定包含從i到k的最短路徑和從k到j的最短路徑（包含編號從0到k-1的結點），且為這兩者之和。 本次循環(huán)后d[i][j]（即dk[i][j]

）必是從i到j的路徑上不含編號為k+1到n-1的結點時的最短路徑長度（僅包含編號從0到k的結點）。那么經過n次循環(huán)后，d[i][j]（即dn-1[i][j]）便是從i到j的路徑上，允許包括所有編號的結點的最短路徑長度。得到問題的最優(yōu)解。補充：7.3矩陣連乘

確定n個矩陣連乘積A0A1...An-1的計算次序，使得按照這一次序計算矩陣連乘積，需要的“數乘”次數最少。

這里矩陣Ai的維數是pi×pi+1。7.4最長公共子序列（定義7-1）若給定序列X=(x1,x2,...,xm)，則另一序列Z=(z1,z2,...,zk)為X的子序列是指 存在一個嚴格遞增下標序列(i1,i2,...ik)使得對于所有j=1,...,k

有zj=xij

。設起始下標為1。

如：序列X=(A,B,C,B,D,A,B)

序列Z=(B,C,D,B)是X的子序列，遞增下標序列為(2,3,5,7)（定義7-2）給定兩個序列X和Y，當另一個序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列?！竟?jié)討論求兩個給定序列X和Y的最長公共子序列（longestcommonsubsequeue,LCS）問題。是否可以用窮舉法求兩個序列X和Y的最長公共子序列？長度為m的序列X有2m個子序列。因此窮舉法求解是指數時間的！(定理7-2）設X=(x1,x2,…,xm)和Y=(y1,y2,…,yn)為兩個序列，Z=(z1,z2,…,zk)是它們的最長公共子序列。則：⑴若xm=yn

→則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長公共子序列；⑵若xm≠yn且zk≠xm

→則Z是Xm-1和Y的最長公共子序列；⑶若xm≠yn且zk≠yn

→則Z是X和Yn-1的最長公共子序列。LCS問題的最優(yōu)解具有最優(yōu)子結構特性，因而適合采用動態(tài)規(guī)劃法求解。（反證）若xm=yn

且zk

≠

xm，則在Z的最后增加xm，成為序列（z1,z2,……,zk,xm)是X和Y長度為k+1的公共子序列。這與Z是X和Y的最長公共子序列矛盾。

導出序列Xm=(x1,x2,…,xm)和Yn=(y1,y2,…,yn)的最長公共子序列的遞推關系：⑴若xm=yn，則先求Xm-1和Yn-1的最長公共子序列，并在其尾部加上xm便得到了Xm和Yn的最長公共子序列；⑵若xm≠yn，則必須分別求解兩個子問題Xm-1和Yn以及Xm和Yn-1的最長公共子序列，這兩個公共子序列中的較長者就是Xm和Yn的最長公共子序列。

使用二維數組c[i][j]來保存Xi=(x1,x2,…,xi)和Yj=(y1,y2,…,yj)的最長公共子序列的長度：當i=0或j=0時，Xi和Yj的最長公共子序列為空序列，故此時c[i][j]=0;若xi=yj

(i,j>0)，則c[i][j]=c[i-1][j-1]+1;若xi≠yj(i,j>0)，則c[i][j]=max{c[i][j-1],c[i-1][j]}。程序7-5classLCS{public:LCS(intnx,intny,char*x,char*y);

//創(chuàng)建二維數組c、s和一維數組a、b，并進行初始化

intLCSLength();

//求最優(yōu)解值（最長公共子序列長度）

voidCLCS();

//構造最優(yōu)解（最長公共子序列）

…….private:

voidCLCS(inti,intj);int**c,**s,m,n; //c[i][j]中保存最優(yōu)解值

char*a,*b;};采用動態(tài)規(guī)劃法進行自底向上求解，可避免重復計算子問題，在多項式時間內完成計算，時間復雜度為O(m*n)。intLCS::LCSLength() //求最長公共子序列的長度{for(inti=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;

for(i=1;i<=m;i++)

//逐行向下

for(intj=1;j<=n;j++)

//從左至右掃描求值

if(x[i]==y[j]) {c[i][j]=c[i-1][j-1]+1;s[i][j]=1;

//由c[i-1][j-1]計算c[i][j]} elseif(c[i-1][j]>=c[i][j-1] {c[i][j]=c[i-1][j];s[i][j]=2;

//由c[i-1][j]得到c[i][j]} else {c[i][j]=c[i][j-1];s[i][j]=3;

//由c[i][j-1]得到c[i][j]}returnc[m][n]; //返回最優(yōu)解值}O(m*n)S[i][j]記錄c[i][j]的值是由三個子問題c[i-1][j-1]+1，c[i-1][j]和c[i][j-1]中的哪一個計算得到的。這一信息將用于構造最長公共子序列。程序7-5classLCS{public:LCS(intnx,intny,char*x,char*y);

//創(chuàng)建二維數組c、s和一維數組a、b，并進行初始化

intLCSLength();//求最優(yōu)解值（最長公共子序列長度）

voidCLCS();

//構造最優(yōu)解（最長公共子序列）

…….private:

voidCLCS(inti,intj);int**c,**s,m,n;char*a,*b;};根據s的值，構造序列Xm和Yn的最長公共子序列：從s[m][n]開始，如果s[i][j]=1，表示它是由Xi-1和Yj-1的最長公共子序列的尾部加上xi(也即yj)形成的；如果s[i][j]=2，表示它與Xi-1和Yj的最長公共子序列相同；如果s[i][j]=3，表示它與Xi和Yj-1的最長公共子序列相同；如果i=0或j=0，則為空子序列。VoidLCS::CLCS(inti,intj)//構造最長公共子序列并輸出{if(i==0||j==0)return; //終止條件

if(s[i][j]==1){

CLCS(i-1,j-1);

cout<<a[i];

//輸出

}elseif(s[i][j]==2)CLCS(i-1,j); elseCLCS(i,j-1);}O(m+n)例7-6

設有兩個序列X=(x1,x2,…,x7)=(a,b,c,b,d,a,b)和Y=(y1,y2,…,y6)=(b,d,c,a,b,a)。求它們的最長公共子序列。012345670123456c[i][j]00000000000000bdcabaYXabcbdab X=(x1,x2,…,x7)=(a,b,c,b,d,a,b)Y=(y1,y2,…,y6)=(b,d,c,a,b,a)012345670123456s[i][j]00000000000000bdcabaYXabcbdab011111101112220122222112223312233341223344212122123221222312222123221231212211323212最長公共子序列的長度為c[7][6]=4由s的值追溯構造最長公共子序列最長公共子序列由所有為1的s[i][j]項對應的xi組成。此處s[6][6]=1，因此取X[6]=a=Y[6]s[4][5]=1，因此取X[4]=b=Y[5]s[3][3]=1，因此取X[3]=c=Y[3]s[2][1]=1，因此取X[2]=b=Y[1]因此最長公共子序列為（x2,x3,x4,x6)=(b,c,b,a)算法的改進1、數組s可以省去

c[i][j]是由c[i][j]=c[i-1][j-1]+1，c[i][j]=c[i-1][j]或c[i][j]=c[i][j-1]計算得來的，要確定c[i][j]是從這三者中哪一個計算得來的，可以直接由c的值確定，而不必借助s。 因此可以寫一個類似的CLCS算法在O(m+n)時間內構造最長公共子序列。思考：是否可能得到多組最長公共子序列？算法的改進2、如果只需計算最長公共子序列的長度（而不用構造最優(yōu)解），那么算法的空間需求還可以大大減少。 式(7-12)中，計算c[i][j]僅用到第i行和第i-1行元素。因此只需兩行元素空間就可以計算最長公共子序列的長度。因此算法的空間復雜度為O(n)。進一步分析可知其為O(min{m,n})備忘錄方法

備忘錄方法的控制結構與自頂向下直接遞歸方法的控制結構相同。

區(qū)別在于備忘錄方法為每個已解過的子問題建立了備忘錄進行保存，以備需要時直接查看，之后不再重復計算。是動態(tài)規(guī)劃法的一種變形。備忘錄方法與動態(tài)規(guī)劃法比較：1、與動態(tài)規(guī)劃法的共同點：用一個表格來保存已求解的子問題的答案，使下次需要解此子問題時，只簡單地查看答案，不重新計算。2、與動態(tài)規(guī)劃法的區(qū)別：備忘錄的遞歸方式是自頂向下，而動態(tài)規(guī)劃法的遞歸方式是自底向上。例：求Fib(4):動態(tài)規(guī)劃法：

Fib(0)->Fib(1)->Fib(2)->Fib(3)->Fib(4)備忘錄：

Fib(4)->Fib(3)->Fib(2)->Fib(1)->Fib(0)備忘錄方法與遞歸方法比較：1、與遞歸方法的共同點：遞歸方式均為自頂向下2、與遞歸方法的區(qū)別：備忘錄方法用一個表格來保存已求解的子問題的答案，使下次需要解此子問題時，只簡單地查看答案，不重新計算；而遞歸方法在每次遇到子問題都要重新計算。如何選擇使用動態(tài)規(guī)劃法或備忘錄法？★當一個問題的所有子問題都至少要解一次時，選用動態(tài)規(guī)劃法較好，此時沒有任何多余的計算，還可利用規(guī)則的表格存取方式，減少時間和空間需求?！锂斠粋€問題只有部分子問題需要求解時，選用備忘錄法較好，它只解那些確實需要求解的子問題。思考：如何用備忘錄方法求解最長公共子序列問題？7.60/1背包一般背包問題——物品可以分割0/1背包問題——物品不可分割0/1背包問題：已知一個載重為M的背包和n件物品，物品編號0~n-1。第i件物品的重量為wi，如果將第i件物品裝入背包將獲利pi。（0≤i≤n-1，wi>0，pi>0）在物品不能分割的情況下，求一種最佳裝載方案使得總收益最大。 0/1背包問題的形式化描述： 給定：M>0，wi>0，pi>0 （0≤i≤n-1)

求：一個n元向量X=(x0,x1,…,xn-1)，xi∈{0,1}

（0≤i≤n-1)

使得：0/1背包問題具有最優(yōu)子結構特性： 設(x0,x1,…,xn-1)，xi∈{0,1}是0/1背包的最優(yōu)解。 那么(x0,x1,…,xn-2)必然是0/1背包子問題的最優(yōu)解。第i件物品的重量為wi，效益pi，wi>0，pi>0，0≤i<n-1。背包載重M-wn-1xn-1，共有n-1件物品。且且因此證明（反證）：若(x0,x1,…,xn-2)不是子問題的最優(yōu)解，而(z0,z1,…,zn-2)是該子問題的最優(yōu)解。則有：顯然(z0,z1,…,zn-2,xn-1)是比(x0,x1,…,xn-1)收益更高的最優(yōu)解，(x0,x1,…,xn-1)不是背包問題的最優(yōu)解。與假設矛盾。因此(x0,x1,…,xn-2)必然是相應子問題的一個最優(yōu)解。給定0/1背包問題的實例KNAP(0,n-1,M)

，求解過程中可能存在重疊子問題現象。實例KNAP(0,n-1,M)通過對n個物品是否加入背包作出一系列決策進行求解，決策次序是(xn-1,xn-2,…,x0)。在對xn-1做出決策后，存在兩種情況：（1）xn-1=1，將編號為n-1的物品加入背包，接著求解子問題KNAP(0,n-2,M-wn-1)；（2）xn-1=0，編號為n-1的物品不加入背包，接著求解子問題KNAP(0,n-2,M)。令f(j,X)表示背包載重為X，可供選擇的物品為0,1,…,j時的最優(yōu)解值(最大收益)，可得遞歸式：編號為j的物品加入背包編號為j的物品不加入背包只有當X≥wj時執(zhí)行該式，否則將只有f(j,X)=f(j-1,X)一種選擇，即：物品wj不加入背包。非法情況，背包載重<0。給定0/1背包問題的實例KNAP(0,n-1,M)

，求解過程中可能存在重疊子問題現象。實例KNAP(0,n-1,M)通過對n個物品是否加入背包作出一系列決策進行求解，決策次序是(xn-1,xn-2,…,x0)。在對xn-1做出決策后，存在兩種情況：（1）xn-1=1，將編號為n-1的物品加入背包，接著求解子問題KNAP(0,n-2,M-wn-1)；（2）xn-1=0，編號為n-1的物品不加入背包，接著求解子問題KNAP(0,n-2,M)。令f(j,X)表示背包載重為X，可供選擇的物品為0,1,…,j時的最優(yōu)解值(最大收益)，可得遞歸式：程序7-80/1背包的遞歸算法classKnapsack{public:Knapsack(intmSize,floatcap,float*wei,T*prof);//構造函數

//用于給n,m,w,p賦值

TRKnap();private:

Tf(intj,floatX);floatm; //背包載重

intn; //物品個數

float*w; //物品重量

T*p; //物品價值}template<classT>TKnapsack<T>::f(intj,floatX) //私有遞歸函數{ //物品0-j放入載重X的背包中的最大收益

if(j<0)return((x<0)?-INFTY:0);if(X<w[j])returnf(j-1,X);//只有一種選擇——不取物品j

else{ Ta=f(j-1,X); Tb=f(j-1,X-w[j])+p[j];//兩種選擇——取或不取物品j if(a>b)returna; elsereturnb;//取其中較大的一種選擇

}}template<classT>TKnapsack<T>::RKnap() //公有函數{if(n>0)return

f(n-1,m);elsereturnNoAns;//一個代表無收益的常量}例7-8

有0/1背包問題n=3，(w0,w1,w2)=(2,3,4)，(p0,p1,p2)=(1,2,4)，M=6，求最優(yōu)解值f(2,6)。遞歸求解過程：

f(2,6)=max{f(1,6),f(1,6-4)+4}=f(1,6)=max{f(0,6),f(0,6-3)+2}=f(1,2)=f(0,2)=f(0,6)=max{f(-1,6),f(-1,6-2)+1}=f(0,3)=max{f(-1,3),f(-1,3-2)+1}=f(0,2)=max{f(-1,2),f(-1,2-2)+1}=111135∵f(-1,y)=0，y≥0程序7-8

template<classT>TKnapsack<T>::f(intj,floatX){ //物品0-j放入載重X的背包中的最大收益

if(j<0)return((x<0)?-INFTY:0);if(X<w[j])returnf(j-1,X);//只有一種選擇——不取物品j

else{ Ta=f(j-1,X); Tb=f(j-1,X-w[j])+p[j];//兩種選擇——取或不取物品j if(a>b)returna; elsereturnb;//取其中較大的一種選擇

}}物品數目為n時，程序的遞歸算法時間為T(n)。則有如下遞推式：

T(0)=T(1)=a T(n)≤2T(n-1)+b該遞推式的解為O(2n)?？梢姵绦?-8：0/1背包問題的遞歸算法時間復雜度最壞情況下為指數級的。由上述遞歸過程可知，可采用動態(tài)規(guī)劃法（或備忘錄法）求解0/1背包問題。當物品重量為整數時，可采用動態(tài)規(guī)劃法，自底向上進行計算。已經計算的子問題的最優(yōu)解值用二維數組f[j][k]保存(0≤j<n，0≤k≤M)。（也可以采用備忘錄方法，在遞歸計算中保存子問題的最優(yōu)解值。）由于需要對j和k的不同值計算f[j][k]，因此總的計算時間為Θ(nM)，其中M是背包載重量，n是物品個數。但是當物品重量和背包載重為實數時，子問題的最優(yōu)解值f(j,X)是X(0≤X≤M)的連續(xù)函數，上述方法便行不通了。物品重量為實數的0/1背包的動態(tài)規(guī)劃算法從式（7-25）f(j,X)的遞推式

可知： 子問題的最優(yōu)解值f(j,X)是X(0≤X≤M)的階梯形單調非減函數。（見例7-8）X<wj時只有f(j-1,X)一種選擇

例7-8

有0/1背包問題n=3，(w0,w1,w2)=(2,3,4)，(p0,p1,p2)=(1,2,4)，M=6，求最優(yōu)解值f(2,6)。最優(yōu)解值f(2,6)=512345678120-∞f(-1,X)X12345678120-∞f(0,X)X12345678120-∞f(1,X)X3函數f是階梯形非減曲線，可以由一組階躍點來描述。1234567812345670﹣∞f(2,X)X9函數f(j,X)是由f(j-1,X)和f(j-1,X-wj)+pj的函數曲線，按X相同時取大值的方式生成的。由于將f(j-1,X)在X軸上右移wj個單位，然后上移pj個單位，就可得到f(j-1,X-wj)+pj的圖像。12345678120-∞f(-1,X)X12345678120-∞f(0,X)X12345678120-∞f(-1,X-w0)+p0X用

表示函數曲線f(j,X)的全部階躍點的集合。用

表示函數曲線f(j-1,X-wj)+pj的全部階躍點的集合。12345678120-∞f(0,X)X12345678120-∞f(1,X)X312345678120-∞f(0,X-w1)+p1X312345678120-∞f(1,X)X31234567812345670﹣∞f(2,X)Xf(1,X-w2)+p21234567812345670﹣∞X被支配的階躍點

計算所有和的步驟如下：，函數f(-1,X)只有一個階躍點。由集合中的每個階躍點(X,P)，得到集合中的一個階躍點(X+wj,P+pj)。是合并集合，并舍棄其中被支配的階躍點和所有X>M的階躍點得到的。載重收益設(X1,P1)和(X2,P2)是兩個階躍點，如果X1<X2而P1>P2，則稱(X1,P1)支配(X2,P2)，或(X2,P2)被(X1,P1)所支配。應舍棄被支配的階躍點(X2,P2)。

（例7-8中）從最優(yōu)解值回溯得到最優(yōu)解：從Sn-1(即S2)中最后一個階躍點(X,P)=(6,5)開始，其中P=5是最優(yōu)解值。判斷(6,5)是和中哪個集合的階躍點：若屬于，則x2=0；否則x2=1。本例中該階躍點在中，因此x2=1。由于x2=1，計算(X-w2,P-p2)=(2,1)，屬于，因此x1=0。由于x1=0，計算(X,P)=(2,1)，屬于，因此x0=1。1234567812345670﹣∞f(2,X)X0/1背包算法的粗略描述程序7-9voidDKP(float*p,float*w,intn,floatM,float&P,int*x){//①生成Si和Si1S-1={(0,0)};for(i=0;i<n-1;i++){ Si1={(X,P)|(X-wi,P-pi)∈Si-1

andX≤M}; //由Si-1得Si1

Si=MergerPurge(Si-1,Si1); //合并兩集合得Si}//②得最優(yōu)解值

(X1,P1)=Sn-2中最后一個階躍點；

(X2,P2)=(X+wn-1,P+pn-1),其中(X,P)是Sn-2中使得X+wn-1≤M的最大的階躍點; //所得(X2,P2)是Sn-11中最后一個階躍點

P=max{P1,P2};//③回溯得到最優(yōu)解

if(P2>P1)xn-1=1;elsexn-1=0;

回溯確定xn-2,xn-3,…,x0;}0/1背包算法的實現

數據結構：使用階躍點序偶(W,P)組成的一維數組p，依次順序存儲集合S0,S1,…,Sn-1的序偶。用一維數組b[i](0≤i<n，n為物品個數)指示集合Si在數組p中的起始序偶的下標。如：例7-8中的階躍點集合

S0={(0,0),(2,1)}S1={(0,0),(2,1),(3,2),(5,3)}S2={(0,0),(2,1),(3,2),(4,4),(6,5)}0123456789101112W(載重)02023502346P

(收益)01012301245pb[0]b[1]b[2]b[3]S-1中只有一個階躍點(0,0)，因此未保存。位于b[n]-1處的P值即為最優(yōu)解值。程序7-10structXP //結構XP定義一個階躍點(X,P){floatX,P; }template<classT>classKnapsack{public:Knapsack(intsz,floatcap,float*wei,T*prof); //構造函數

TDKnap(int*x); //公有調用接口，最優(yōu)解由x帶回

……private:TDKnap();

//求最優(yōu)解值（最大收益）

voidTraceBack(int*x);

//回溯得最優(yōu)解

intLargest(intlow,inthigh,inti);//在Si-1中求使得p[u].X+w[i]≤m的最大下標ufloatm,*w; //m為背包載重，w[i]為物品重量

T*pf; //pf[i]為物品價值

XP*p; //p數組依次存放集合S0,S1,…,Sn-1中的序偶

intn,*b; //n為物品件數，b[i]指示集合Si在數組p中的起始序偶下標}0/1背包最優(yōu)解值算法（1）程序7-10template<classT>intKnapsack<T>::Largest(intlow,inthigh,inti)//在Si-1中（在數組p中下標從low到high）求使得p[u].X+w[i]≤m的最大下標，//則生成Si1時，只需考慮Si-1中下標不超過u的元素。{intu=low-1; //給u賦初值

for(intj=low;j<=high;j++){ floatww=p[j].X+w[i]; if(ww<=m)u=j; //更新u值

}returnu;}0/1背包最優(yōu)解值算法（2）程序7-10template<classT>TKnapsack<T>::DKnap() //返回最優(yōu)解值（最大收益）{floatww,pp;intnext;//始終指向數組p中下一空閑存儲位置（Si中即將寫入的位置）

b[0]=0;//S0在數組p中的起始序偶的下標

p[0].X=p[0].P=0.0; p[1].X=w[0];p[1].P=pf[0]; //S0賦初值

intlow=0,high=1;//S0的起、止位置（Si-1的首個和最后一個階躍點位置）

b[1]=next=2;//next指示了數組p的下一個空閑位置（S1中即將寫入的位置）

//low和cost指示S0中階躍點序偶的范圍（起、止位置）

……未完待續(xù)0/1背包最優(yōu)解值算法（3）程序7-10for(inti=1;i<=n-1;i++)//每次循環(huán)生成一個Si //用k掃描并檢查Si-1中的序偶，復制到Si中去，并舍棄被支配的序偶

{intk=low;//k負責掃描Si-1intu=Largest(low,high,i);//生成Si1時，只需考慮Si-1中下標不超過u的

for(intj=low;j<=u;j++) {//（由Si-1）依次生成Si1中的每個階躍點，同時合并到Si中

ww=p[j].X+w[i];pp=p[j].P+pf[i];//(1)生成Si1中的一個階躍點(ww,pp) while((k<=high)&&(p[k].X<ww))//(2)將Si-1中所有X<ww的序偶都加入Si {p[next].X=p[k].X;p[next++].P=p[k++].P;} if((k<=high)&&(p[k].X==ww))//(3)若Si-1中有X==ww的序偶

if(pp<p[k].P)pp=p[k++].P;//則將P和pp中較大者作為pp的新值

if(pp>p[next-1].P)//若(ww,pp)不被支配，則加入Si中，否則舍棄

{p[next].X=ww;p[next++].P=pp;} while((k<=high)&&(p[k].P<=p[next-1].P)k++; //(4)