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

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

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

7.1一般方法和基本要素

7.2每對結(jié)點(diǎn)間的最短路徑

7.4最長公共子序列

7.60/1背包7.1一般方法和基本要素動態(tài)規(guī)劃算法總體思想動態(tài)規(guī)劃算法的基本要素設(shè)計(jì)動態(tài)規(guī)劃算法的步驟動態(tài)規(guī)劃法與分治法、貪心法的區(qū)別動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題動態(tài)規(guī)劃算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。動態(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)如果能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。動態(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)子結(jié)構(gòu)性質(zhì)——用動態(tài)規(guī)劃法求解的前提。

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

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

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

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

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

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

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

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

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

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

(1≤i≤k)

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

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

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

證明（多段圖具有最優(yōu)子結(jié)構(gòu)性質(zhì)）如果(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)更短。 與假設(shè)矛盾！多段圖的最優(yōu)子結(jié)構(gòu)性質(zhì)得證！在分析（證明）問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。多段圖問題的遞推式（向前遞推）

由多段圖問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，容易得到多段圖問題的遞推式，從而由子問題的最優(yōu)解來計(jì)算原問題的最優(yōu)解： 多段圖問題的向前遞推式：（式7-1）cost(i,j)是從第i階段中的結(jié)點(diǎn)j，到匯點(diǎn)t的最短路徑長度。cost(i+1,p)是從后繼結(jié)點(diǎn)（第i+1階段中的結(jié)點(diǎn)）p到匯點(diǎn)t的最短路徑長度。（子問題的最優(yōu)解）c(j,p)+cost(i+1,p)是從第i階段結(jié)點(diǎn)j，經(jīng)過第i+1階段結(jié)點(diǎn)p到達(dá)匯點(diǎn)t的路徑長度。cost(i,j)則是這些路徑中的最短路徑長度。<j,p>E表示j,p之間有邊01234567891011源點(diǎn)st匯點(diǎn)97321242711118654356524v1v2v3v4v5階段使用式（7-1）向前遞推式，由后向前計(jì)算最優(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源點(diǎn)st匯點(diǎn)97321242711118654356524v1v2v3v4v5階段若想求最優(yōu)解，必須在計(jì)算最優(yōu)解值的過程中保存一些必要信息?？捎胐(i,j)來記錄從第i階段結(jié)點(diǎn)j到匯點(diǎn)t的最短路徑上該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)編號。根據(jù)前面例7-1求最優(yōu)解值cost(1,0)的過程中，產(chǎn)生的中間結(jié)果：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的值確定最短路徑上的結(jié)點(diǎn)，得到兩條最短路徑：(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)多段圖顯然具有重疊子問題性質(zhì)：計(jì)算cost(3,7)、cost(3,6)、cost(3,5)時(shí)都要用到cost(4,9)的值，因此保存cost(4,9)的值可以避免重復(fù)計(jì)算。程序7-1：多段圖的向前遞推動態(tài)規(guī)劃算法FMultiGraph(intk,int*p) //共k個(gè)階段，n個(gè)結(jié)點(diǎn){//帶權(quán)有向圖G（多段圖）采用鄰接表存儲（見程序6-8）

float*cost=newfloat[n];//一維數(shù)組cost[j]保存結(jié)點(diǎn)j到匯點(diǎn)t的最短路徑

int*d=newint[n];//一維數(shù)組d[j]保存cost[j]對應(yīng)的最短路徑上的下一個(gè)結(jié)點(diǎn)

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

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

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

{ intv=r->adjVex; //當(dāng)前階段的結(jié)點(diǎn)j與下一階段的結(jié)點(diǎn)v之間有邊

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

cost[j]=min;d[j]=q;//q是最短子路徑上j的下一個(gè)結(jié)點(diǎn)編號

}

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

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

p[j]=d[p[j-1]];//數(shù)組p[]保存最優(yōu)解，p[i]是最短路徑上第i階段結(jié)點(diǎn)}前提：結(jié)點(diǎn)已按拓?fù)漤樞蚺判颉Ｋ伎迹喝绾蔚玫?？程?-1：多段圖的向前遞推動態(tài)規(guī)劃算法FMultiGraph(intk,int*p) //共k個(gè)階段，n個(gè)結(jié)點(diǎn){//帶權(quán)有向圖G（多段圖）采用鄰接表存儲（見程序6-8）

float*cost=newfloat[n];//一維數(shù)組cost[j]保存結(jié)點(diǎn)j到匯點(diǎn)t的最短路徑

int*d=newint[n];//一維數(shù)組d[j]保存cost[j]對應(yīng)的最短路徑上的下一個(gè)結(jié)點(diǎn)

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

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

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

{ intv=r->adjVex; //當(dāng)前階段的結(jié)點(diǎn)j與下一階段的結(jié)點(diǎn)v之間有邊

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

cost[j]=min;d[j]=q;//q是最短子路徑上j的下一個(gè)結(jié)點(diǎn)編號

}

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

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

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

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

——關(guān)鍵路徑問題

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

若AOE網(wǎng)絡(luò)中的結(jié)點(diǎn)已經(jīng)按拓?fù)湫蛄械拇涡蚓幪?則(1)對帶權(quán)有向圖G進(jìn)行拓?fù)渑判?確認(rèn)其是否為無環(huán)圖;(2)按拓?fù)浯涡蛴?jì)算earliest[i],0≤i≤n-1;(3)按逆拓?fù)浯涡蛴?jì)算latest[i],0≤i≤n-1;(4)對每一條邊<i,j>計(jì)算latest[j]-earliest[i],并檢查latest[j]-earliest[i]是否等于w[i][j],w[i][j]是邊<i,j>的權(quán),從而確定關(guān)鍵活動(邊).從前向后遞推求earliest(j):

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

如:<0,1>,<1,4>,<4,7>,<7,8>就是關(guān)鍵活動.由關(guān)鍵活動組成的關(guān)鍵路徑為(0,1,4,7,8),長度為19.關(guān)鍵路徑上的所有結(jié)點(diǎn)i滿足earliest(i)=latest(i)。以鄰接表作存儲結(jié)構(gòu)；從源點(diǎn)V0出發(fā)，令earliest[0]=0,按拓?fù)湫蛄星蟾黜旤c(diǎn)的earliest[i]；從匯點(diǎn)Vn-1出發(fā)，令latest[n-1]=earliest[n-1],按逆拓?fù)湫蛄星笃溆喔黜旤c(diǎn)的latest[i]；若每條弧ak關(guān)聯(lián)的邊為<vi,vj>，根據(jù)各頂點(diǎn)的earliest和latest值，計(jì)算每條弧的early[k]=earliest(i)和late[k]=latest(j)-w(i,j),找出early[k]=late[k]的關(guān)鍵活動。算法實(shí)現(xiàn)template<classT>voidExtLGraph<T>::Earliest(int*earliest,int*order)//求各頂點(diǎn)的earliest[i]{for(inti=0;i<n;i++)earliest[i]=0;for(i=0;i<n;i++) //從前向后{

//前提：圖的拓?fù)渑判蚪Y(jié)果已存在于order數(shù)組中

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

{

//圖的拓?fù)渑判蚪Y(jié)果已存在于order數(shù)組中

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[]值

}}

性能分析關(guān)鍵路徑算法與拓?fù)渑判蛴邢嗤臅r(shí)間復(fù)雜度，其時(shí)間復(fù)雜度為O(n+e)。課堂練習(xí)：求下圖中的關(guān)鍵路徑和關(guān)鍵活動8765342105413322634142012345678earliest(i)025457111014latest(i)036457111014<0,3>,<3,4>,<3,5>,<4,6>,<5,7>,<6,8>,<7,8>是關(guān)鍵活動.因此關(guān)鍵路徑有(0,3,4,6,8)和(0,3,5,7,8),

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

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

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

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]; }}容易看出弗洛伊德算法的時(shí)間復(fù)雜度為O(n3)弗洛伊德算法的正確性證明定理7-1：弗洛伊德算法得到的d[i][j](0≤i,j≤n-1)是從i到j(luò)的最短路徑。證明：（歸納法）初始時(shí)d[i][j]=w[i][j]，從i到j(luò)路徑上沒有其他結(jié)點(diǎn)，因此正確。歸納假設(shè)：在k次循環(huán)后算法正確，d[i][j]（即dk-1[i][j])為從i到j(luò)的路徑上不含編號從k到n-1的結(jié)點(diǎn)時(shí)的最短路徑長度。第k+1次循環(huán)中執(zhí)行：若d[i][k]+d[k][j]<d[i][j]（即dk-1[i][j]

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

）。 因?yàn)橛勺顑?yōu)子結(jié)構(gòu)性質(zhì)：若i到j(luò)的最短路徑經(jīng)過k，則必定包含從i到k的最短路徑和從k到j(luò)的最短路徑（包含編號從0到k-1的結(jié)點(diǎn)），且為這兩者之和。 本次循環(huán)后d[i][j]（即dk[i][j]

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

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

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

有zj=xij

。設(shè)起始下標(biāo)為1。

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

序列Z=(B,C,D,B)是X的子序列，遞增下標(biāo)序列為(2,3,5,7)（定義7-2）給定兩個(gè)序列X和Y，當(dāng)另一個(gè)序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。——本節(jié)討論求兩個(gè)給定序列X和Y的最長公共子序列（longestcommonsubsequeue,LCS）問題。是否可以用窮舉法求兩個(gè)序列X和Y的最長公共子序列？長度為m的序列X有2m個(gè)子序列。因此窮舉法求解是指數(shù)時(shí)間的！(定理7-2）設(shè)X=(x1,x2,…,xm)和Y=(y1,y2,…,yn)為兩個(gè)序列，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)子結(jié)構(gòu)特性，因而適合采用動態(tài)規(guī)劃法求解。（反證）若xm=yn

且zk

≠

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

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

使用二維數(shù)組c[i][j]來保存Xi=(x1,x2,…,xi)和Yj=(y1,y2,…,yj)的最長公共子序列的長度：當(dāng)i=0或j=0時(shí)，Xi和Yj的最長公共子序列為空序列，故此時(shí)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)建二維數(shù)組c、s和一維數(shù)組a、b，并進(jìn)行初始化

intLCSLength();

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

voidCLCS();

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

…….private:

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

char*a,*b;};采用動態(tài)規(guī)劃法進(jìn)行自底向上求解，可避免重復(fù)計(jì)算子問題，在多項(xiàng)式時(shí)間內(nèi)完成計(jì)算，時(shí)間復(fù)雜度為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]計(jì)算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]的值是由三個(gè)子問題c[i-1][j-1]+1，c[i-1][j]和c[i][j-1]中的哪一個(gè)計(jì)算得到的。這一信息將用于構(gòu)造最長公共子序列。程序7-5classLCS{public:LCS(intnx,intny,char*x,char*y);

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

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

voidCLCS();

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

…….private:

voidCLCS(inti,intj);int**c,**s,m,n;char*a,*b;};根據(jù)s的值，構(gòu)造序列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)//構(gòu)造最長公共子序列并輸出{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

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

備忘錄方法的控制結(jié)構(gòu)與自頂向下直接遞歸方法的控制結(jié)構(gòu)相同。

區(qū)別在于備忘錄方法為每個(gè)已解過的子問題建立了備忘錄進(jìn)行保存，以備需要時(shí)直接查看，之后不再重復(fù)計(jì)算。是動態(tài)規(guī)劃法的一種變形。備忘錄方法與動態(tài)規(guī)劃法比較：1、與動態(tài)規(guī)劃法的共同點(diǎn)：用一個(gè)表格來保存已求解的子問題的答案，使下次需要解此子問題時(shí)，只簡單地查看答案，不重新計(jì)算。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、與遞歸方法的共同點(diǎn)：遞歸方式均為自頂向下2、與遞歸方法的區(qū)別：備忘錄方法用一個(gè)表格來保存已求解的子問題的答案，使下次需要解此子問題時(shí)，只簡單地查看答案，不重新計(jì)算；而遞歸方法在每次遇到子問題都要重新計(jì)算。如何選擇使用動態(tài)規(guī)劃法或備忘錄法？★當(dāng)一個(gè)問題的所有子問題都至少要解一次時(shí)，選用動態(tài)規(guī)劃法較好，此時(shí)沒有任何多余的計(jì)算，還可利用規(guī)則的表格存取方式，減少時(shí)間和空間需求?！锂?dāng)一個(gè)問題只有部分子問題需要求解時(shí)，選用備忘錄法較好，它只解那些確實(shí)需要求解的子問題。思考：如何用備忘錄方法求解最長公共子序列問題？7.60/1背包一般背包問題——物品可以分割0/1背包問題——物品不可分割0/1背包問題：已知一個(gè)載重為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)

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

（0≤i≤n-1)

使得：0/1背包問題具有最優(yōu)子結(jié)構(gòu)特性： 設(shè)(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)解。與假設(shè)矛盾。因此(x0,x1,…,xn-2)必然是相應(yīng)子問題的一個(gè)最優(yōu)解。給定0/1背包問題的實(shí)例KNAP(0,n-1,M)

，求解過程中可能存在重疊子問題現(xiàn)象。實(shí)例KNAP(0,n-1,M)通過對n個(gè)物品是否加入背包作出一系列決策進(jì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時(shí)的最優(yōu)解值(最大收益)，可得遞歸式：編號為j的物品加入背包編號為j的物品不加入背包只有當(dāng)X≥wj時(shí)執(zhí)行該式，否則將只有f(j,X)=f(j-1,X)一種選擇，即：物品wj不加入背包。非法情況，背包載重<0。給定0/1背包問題的實(shí)例KNAP(0,n-1,M)

，求解過程中可能存在重疊子問題現(xiàn)象。實(shí)例KNAP(0,n-1,M)通過對n個(gè)物品是否加入背包作出一系列決策進(jì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時(shí)的最優(yōu)解值(最大收益)，可得遞歸式：程序7-80/1背包的遞歸算法classKnapsack{public:Knapsack(intmSize,floatcap,float*wei,T*prof);//構(gòu)造函數(shù)

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

TRKnap();private:

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

intn; //物品個(gè)數(shù)

float*w; //物品重量

T*p; //物品價(jià)值}template<classT>TKnapsack<T>::f(intj,floatX) //私有遞歸函數(shù){ //物品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() //公有函數(shù){if(n>0)return

f(n-1,m);elsereturnNoAns;//一個(gè)代表無收益的常量}例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;//取其中較大的一種選擇

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

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

可知： 子問題的最優(yōu)解值f(j,X)是X(0≤X≤M)的階梯形單調(diào)非減函數(shù)。（見例7-8）X<wj時(shí)只有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函數(shù)f是階梯形非減曲線，可以由一組階躍點(diǎn)來描述。1234567812345670﹣∞f(2,X)X9函數(shù)f(j,X)是由f(j-1,X)和f(j-1,X-wj)+pj的函數(shù)曲線，按X相同時(shí)取大值的方式生成的。由于將f(j-1,X)在X軸上右移wj個(gè)單位，然后上移pj個(gè)單位，就可得到f(j-1,X-wj)+pj的圖像。12345678120-∞f(-1,X)X12345678120-∞f(0,X)X12345678120-∞f(-1,X-w0)+p0X用

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

表示函數(shù)曲線f(j-1,X-wj)+pj的全部階躍點(diǎn)的集合。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被支配的階躍點(diǎn)

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

（例7-8中）從最優(yōu)解值回溯得到最優(yōu)解：從Sn-1(即S2)中最后一個(gè)階躍點(diǎn)(X,P)=(6,5)開始，其中P=5是最優(yōu)解值。判斷(6,5)是和中哪個(gè)集合的階躍點(diǎn)：若屬于，則x2=0；否則x2=1。本例中該階躍點(diǎn)在中，因此x2=1。由于x2=1，計(jì)算(X-w2,P-p2)=(2,1)，屬于，因此x1=0。由于x1=0，計(jì)算(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中最后一個(gè)階躍點(diǎn)；

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

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

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

回溯確定xn-2,xn-3,…,x0;}0/1背包算法的實(shí)現(xiàn)

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

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中只有一個(gè)階躍點(diǎn)(0,0)，因此未保存。位于b[n]-1處的P值即為最優(yōu)解值。程序7-10structXP //結(jié)構(gòu)XP定義一個(gè)階躍點(diǎn)(X,P){floatX,P; }template<classT>classKnapsack{public:Knapsack(intsz,floatcap,float*wei,T*prof); //構(gòu)造函數(shù)

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

……private:TDKnap();

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

voidTraceBack(int*x);

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

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

T*pf; //pf[i]為物品價(jià)值

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

intn,*b; //n為物品件數(shù)，b[i]指示集合Si在數(shù)組p中的起始序偶下標(biāo)}0/1背包最優(yōu)解值算法（1）程序7-10template<classT>intKnapsack<T>::Largest(intlow,inthigh,inti)//在Si-1中（在數(shù)組p中下標(biāo)從low到high）求使得p[u].X+w[i]≤m的最大下標(biāo)，//則生成Si1時(shí)，只需考慮Si-1中下標(biāo)不超過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;//始終指向數(shù)組p中下一空閑存儲位置（Si中即將寫入的位置）

b[0]=0;//S0在數(shù)組p中的起始序偶的下標(biāo)

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的首個(gè)和最后一個(gè)階躍點(diǎn)位置）

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

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

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

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

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

ww=p[j].X+w[i];pp=p[j].P+pf[i];//(1)生成Si1中的一個(gè)階躍點(diǎn)(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)