一、最長(zhǎng)公共子序列
??若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的 子序列 是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列{i1,i2,…,ik}使得對(duì)于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相應(yīng)的遞增下標(biāo)序列為{2，3，5，7}。
??給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。
??給定2個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的 最長(zhǎng)公共子序列。
1.1 最長(zhǎng)公共子序列的結(jié)構(gòu)
??設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列為Z={z1,z2,…,zk} ，則
??(1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長(zhǎng)公共子序列。
??(2)若xm≠yn且zk≠xm，則 Z是xm-1和Y的最長(zhǎng)公共子序列。
??(3)若xm≠yn且zk≠yn，則 Z是X和yn-1的最長(zhǎng)公共子序列。
??由此可見(jiàn)，2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
1.2 子問(wèn)題的遞歸結(jié)構(gòu)
??由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：
1.3 計(jì)算最優(yōu)值
??由于在所考慮的子問(wèn)題空間中，總共有θ(mn)個(gè)不同的子問(wèn)題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。
void LCSLength(int m，int n，char *x，char *y，int **c，int **b)
{
int i，j;
for (i = 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 (j = 1; j <= n; j++) {
if (x[i]==y[j]) {
c[i][j]=c[i-1][j-1]+1; b[i][j]=1;}
else if (c[i-1][j]>=c[i][j-1]) {
c[i][j]=c[i-1][j]; b[i][j]=2;}
else { c[i][j]=c[i][j-1]; b[i][j]=3; }
}
}
//構(gòu)造最長(zhǎng)公共子序列
void LCS(int i，int j，char *x，int **b)
{
if (i ==0 || j==0) return;
if (b[i][j]== 1){ LCS(i-1，j-1，x，b); cout<<x[i]; }
else if (b[i][j]== 2) LCS(i-1，j，x，b);
else LCS(i，j-1，x，b);
}
1.4 舉例說(shuō)明
1.5 算法的改進(jìn)
??在算法lcsLength和lcs中，可進(jìn)一步將數(shù)組b省去。事實(shí)上，數(shù)組元素c[i][j]的值僅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]這3個(gè)數(shù)組元素的值所確定。對(duì)于給定的數(shù)組元素c[i][j]，可以不借助于數(shù)組b而僅借助于c本身在時(shí)間內(nèi)確定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一個(gè)值所確定的。
?? 如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求可大大減少。
??事實(shí)上，在計(jì)算c[i][j]時(shí)，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。進(jìn)一步的分析還可將空間需求減至O(min(m,n))。
二、最大子段和
??子段：數(shù)列中的連續(xù)若干子數(shù)列的集合
??問(wèn)題：給定由n個(gè)整數(shù)（可能為負(fù)整數(shù)）組成的序列a1,a2,…an，求該序列的子段和的最大值
??當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)，定義其最大子段和為零
??例如，當(dāng)（a1,a2,a3,a4,a5,a6）=（-2,11,-4,13,-5,-2）時(shí)，最大子段和為20。
2.1 代碼
int MaxSum(int n,int *a){
int besti,bestj;
int i,j,k,thissum;
int sum=0;
for(i=1;i<=n;i++){
for(j=i;j<=n;j++){
thissum=0;
for(k=i;k<=j;k++)
thissum+=a[k];
if (thissum>sum){
sum=thissum;
besti=i;
bestj=j;
}
}
}
return sum;
}
2.2 最大子段和問(wèn)題的分治算法
??將所給的序列a[1:n]，分成長(zhǎng)度相等的兩端a[1:n/2]和 a[n/2+1:n]，分別求出這兩端的最大子段和，則 a[1:n]的最大子段和有三種情況：
??a[1:n]的最大子段和與a[1:n/2]的最大子段和相同；
??a[1:n]的最大子段和與a[n/2+1:n]的最大子段和相同；
??a[1:n]的最大子段和跨越a[1:n/2]和a[n/2+1:n]兩個(gè)區(qū)域。
??對(duì)于3，容易看出，a[n/2]與a[n/2+1]必在最優(yōu)子序列中！
??在a[1:n/2]中計(jì)算出s1為含有a[n/2]的最大子段和。
??在a[n/2+1:n]中計(jì)算出s2為含有a[n/2+1]的最大子段和。
??則s1+s2即為出現(xiàn)情形3時(shí)的最優(yōu)值。
int MaxSubSum(int *a,int left,int right){
int sum=0;
int center;
int leftsum,rightsum;
int i,s1,s2,lefts,rights;
if(left==right)
sum=a[left]>0?a[left]:0;
else{
center=(left+right)/2;
leftsum=MaxSubSum(a,left,center);
rightsum=MaxSubSum(a,center+1,right);
s1=0;
lefts=0;
for(i=center;i>=left;i--){
lefts+=a[i];
if(lefts>s1)
s1=lefts;
}
s2=0;
rights=0;
for(i=center+1;i<=right;i++){
rights+=a[i];
if(rights>s2)
s2=rights;
}
2.3 代碼
sum=s1+s2;
if(sum<leftsum)
sum=leftsum;
if(sum<rightsum)
sum=rightsum;
}
return sum;
}
2.4 分治算法的時(shí)間復(fù)雜度
??該算法所需的計(jì)算時(shí)間T(n)滿足典型的分治算法遞歸式。
??解此遞歸方程可知，T(n)= O(nlogn)。
2.5 最大子段和問(wèn)題的動(dòng)態(tài)規(guī)劃算法
??若記b[j]為必須包含a[j]的左側(cè)連續(xù)數(shù)據(jù)的最大子段和，則所求的最大子段和為max(1到n) b[j]，再用變量sum存儲(chǔ)當(dāng)前b[j]的最大值即可。
??由于程序只用了一個(gè)for循環(huán)，所以此算法的時(shí)間復(fù)雜度為O(n)。
??由b[j]的定義易知：
??當(dāng)b[j-1]>0 時(shí)，b[j]= b[j-1]+a[j]，否則b[j]= a[j]。由此可得b[j]的動(dòng)態(tài)規(guī)劃遞歸式b[j]= max{b[j-1]+a[j],a[j]}，1<=j<=n。
??據(jù)此，可以設(shè)計(jì)出求最大字段和的動(dòng)態(tài)規(guī)劃算法。
??代碼如下：
int MaxSum(int n,int *a){
int i,sum=0,b=0;
for(i=1;i<=n;i++){
if(b>0)
b+=a[i];
else
b=a[i];
if(b>sum)
sum=b;
}
return sum;
}
三、凸多邊形最優(yōu)三角剖分
??用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即P={v0,v1,…,vn-1}表示具有n條邊的凸多邊形。
??若vi與vj是多邊形上不相鄰的2個(gè)頂點(diǎn)，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成2個(gè)多邊形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。
??多邊形的三角剖分是將多邊形分割成互不相交的三角形的弦的集合T。
??給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權(quán)之和為最小。
3.1 三角剖分的結(jié)構(gòu)及其相關(guān)問(wèn)題
??一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹(shù)，稱為表達(dá)式的語(yǔ)法樹(shù)。例如，完全加括號(hào)的矩陣連乘積((A1(A2A3))(A4(A5A6)))所相應(yīng)的語(yǔ)法樹(shù)如圖 (a)所示。
??凸多邊形{v0,v1,…vn-1}的三角剖分也可以用語(yǔ)法樹(shù)表示。例如，圖 (b)中凸多邊形的三角剖分可用圖 (a)所示的語(yǔ)法樹(shù)表示。
??矩陣連乘積中的每個(gè)矩陣Ai對(duì)應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，i<j，對(duì)應(yīng)于矩陣連乘積A[i+1:j]。
3.2 最優(yōu)子結(jié)構(gòu)性質(zhì)
??凸多邊形的最優(yōu)三角剖分問(wèn)題有最優(yōu)子結(jié)構(gòu)性質(zhì)。
??事實(shí)上，若凸(n+1)邊形P={v0,v1,…,vn-1}的最優(yōu)三角剖分T包含三角形v0vkvn，1≤k≤n-1，則T的權(quán)為3個(gè)部分權(quán)的和：三角形v0vkvn的權(quán)，子多邊形{v0,v1,…,vk}和{vk,vk+1,…,vn}的權(quán)之和。
??可以斷言，由T所確定的這2個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲衶v0,v1,…,vk}或{vk,vk+1,…,vn}的更小權(quán)的三角剖分將導(dǎo)致T不是最優(yōu)三角剖分的矛盾。
3.3 最優(yōu)三角剖分的遞歸結(jié)構(gòu)
??定義t[i][j]，1≤i<j≤n為凸子多邊形{vi-1,vi,…,vj}的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值。為方便起見(jiàn)，設(shè)退化的多邊形{vi-1,vi}具有權(quán)值0。據(jù)此定義，要計(jì)算的凸(n+1)邊形P的最優(yōu)權(quán)值為t[1][n]。
??t[i][j]的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算。當(dāng)j-i≥1時(shí)，凸子多邊形至少有3個(gè)頂點(diǎn)。由最優(yōu)子結(jié)構(gòu)性質(zhì)，t[i][j]的值應(yīng)為t[i][k]的值加上t[k+1][j]的值，再加上三角形vi-1vkvj的權(quán)值，其中i≤k≤j-1。由于在計(jì)算時(shí)還不知道k的確切位置，而k的所有可能位置只有j-i個(gè)，因此可以在這j-i個(gè)位置中選出使t[i][j]值達(dá)到最小的位置。由此，t[i][j]可遞歸地定義為：
四、圖像壓縮
??圖象的變位壓縮存儲(chǔ)格式將所給的象素點(diǎn)序列{p1,p2,…,pn},0≤pi≤255分割成m個(gè)連續(xù)段S1,S2,…,Sm。第i個(gè)象素段Si中(1≤i≤m)，有l(wèi)[i]個(gè)象素,且該段中每個(gè)象素都只用b[i]位表示。
??設(shè)
??則第i個(gè)象素段Si為
??設(shè)
，則hi?b[i]?8。因此需要用3位表示b[i],如果限制1?l[i]?255，則需要用8位表示l[i]。因此，第i個(gè)象素段所需的存儲(chǔ)空間為l[i]*b[i]+11位。按此格式存儲(chǔ)象素序列{p1,p2,…,pn}，需要
位的存儲(chǔ)空間。
??圖象壓縮問(wèn)題要求確定象素序列{p1,p2,…,pn}的最優(yōu)分段，使得依此分段所需的存儲(chǔ)空間最少。每個(gè)分段的長(zhǎng)度不超過(guò)256位。
??設(shè)l[i]，b[i]，是{p1,p2,…,pn}的最優(yōu)分段。顯而易見(jiàn)，l[1]，b[1]是{p1,…,pl[1]}的最優(yōu)分段，且l[i]，b[i]，是{pl[1]+1,…,pn}的最優(yōu)分段。即圖象壓縮問(wèn)題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。
設(shè)s[i]，1≤i≤n，是象素序列{p1,…,pn}的最優(yōu)分段所需的存儲(chǔ)位數(shù)。由最優(yōu)子結(jié)構(gòu)性質(zhì)易知：
??其中，
??算法復(fù)雜度分析：
??由于算法compress中對(duì)k的循環(huán)次數(shù)不超這256，故對(duì)每一個(gè)確定的i，可在時(shí)間O(1)內(nèi)完成的計(jì)算。因此 整個(gè)算法所需的計(jì)算時(shí)間為O(n)。
五、電路布線
??在一塊電路板的上、下2端分別有n個(gè)接線柱。根據(jù)電路設(shè)計(jì)，要求用導(dǎo)線(i,π(i))將上端接線柱與下端接線柱相連，如圖所示。其中π(i)是{1,2,…,n}的一個(gè)排列。導(dǎo)線(i,π(i))稱為該電路板上的第i條連線。對(duì)于任何1≤i<j≤n，第i條連線和第j條連線相交的充分且必要的條件是π(i)>π(j)。
??電路布線問(wèn)題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說(shuō)，該問(wèn)題要求確定導(dǎo)線集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。
??記
??N(i,j)的最大不相交子集為MNS(i,j)。Size(i,j)=|MNS(i,j)|。
??(1)當(dāng)i=1時(shí)，
??(2)當(dāng)i>1時(shí)，
??若j<π(i)。此時(shí)，
??故在這種情況下，N(i,j)=N(i-1,j)，從而Size(i,j)=Size(i-1,j)。
2.2 j≥π(i)，(i,π(i))∈MNS(i,j) 。 則對(duì)任意(t,π(t)) ∈MNS(i,j)有t<i且π(t)<π(i)。在這種情況下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集。
??若
??則對(duì)任意(t,π(t)) ∈MNS(i,j)有t<i。從而
??因此，Size(i,j)≤Size(i-1,j)。
??另一方面，
??故又有Size(i,j)≥Size(i-1,j)，從而Size(i,j)=Size(i-1,j)。
5.1 代碼
void MNS(int C[],int n){
int i,j;
for(j=0;j<C[1];j++){
size[1][j]=0;
}
for(j=C[1];j<=n;j++){
size[1][j]=1;
}
for(i=2;i<n;i++){
for(j=0;j<C[i];j++){
size[i][j]=size[i-1][j];
}
for(j=C[i];j<=n;j++){
size[i][j]=size[i-1][j]>(size[i-1][C[i]-1]+1)?size[i-1][j]:(size[i-1][C[i]-1]+1);
}
}
size[n][n]=size[n-1][n]>(size[n-1][C[n]-1]+1)?size[n-1][n]:(size[n-1][C[n]-1]+1);
}
void Traceback(int C[],int n,int NET[]){
int i,j=n;
int m=0;
for(i=n;i>1;i--){
if(size[i][j]!=size[i-1][j]){
NET[m++]=i;
j=C[i]-1;
}
if(j>=C[1])
NET[m++]=1;
}
}
六、流水作業(yè)調(diào)度
??n個(gè)作業(yè){1，2，…，n}要在由2臺(tái)機(jī)器M1和M2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時(shí)間分別為ai和bi。
??流水作業(yè)調(diào)度問(wèn)題要求確定這n個(gè)作業(yè)的最優(yōu)加工順序，使得從第一個(gè)作業(yè)在機(jī)器M1上開(kāi)始加工，到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少。
??分析：
??直觀上，一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器M1沒(méi)有空閑時(shí)間，且機(jī)器M2的空閑時(shí)間最少。在一般情況下，機(jī)器M2上會(huì)有機(jī)器空閑和作業(yè)積壓2種情況。
??設(shè)全部作業(yè)的集合為N={1，2，…，n}。S?N是N的作業(yè)子集。在一般情況下，機(jī)器M1開(kāi)始加工S中作業(yè)時(shí)，機(jī)器M2還在加工其它作業(yè)，要等時(shí)間t后才可利用。將這種情況下完成S中作業(yè)所需的最短時(shí)間記為T(mén)(S,t)。流水作業(yè)調(diào)度問(wèn)題的最優(yōu)值為T(mén)(N,0)。
??設(shè)π是所給n個(gè)流水作業(yè)的一個(gè)最優(yōu)調(diào)度，它所需的加工時(shí)間為 aπ(1)+T’。其中T’是在機(jī)器M2的等待時(shí)間為bπ(1)時(shí)，安排作業(yè)π(2)，…，π(n)所需的時(shí)間。
??記S=N-{π(1)}，則有T’=T(S,bπ(1))。
??證明：事實(shí)上，由T的定義知T’≤T(S,bπ(1))。若T’>T(S,bπ(1))，設(shè)π’是作業(yè)集S在機(jī)器M2的等待時(shí)間為bπ(1)情況下的一個(gè)最優(yōu)調(diào)度。則π(1)， π’(2)，…， π’(n)是N的一個(gè)調(diào)度，且該調(diào)度所需的時(shí)間為aπ(1)+T(S,bπ(1))<aπ(1)+T’。這與π是N的最優(yōu)調(diào)度矛盾。故T’≤T(S,bπ(1))。從而T’=T(S,bπ(1))。這就證明了流水作業(yè)調(diào)度問(wèn)題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。
??由 流水作業(yè)調(diào)度問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì) 可知，
七、投資問(wèn)題
??問(wèn)題：m元錢(qián)，n項(xiàng)投資，fi(x)：將x元投入第i個(gè)項(xiàng)目的效益。求使得總效益最大的投資方案。
??建模：?jiǎn)栴}的解是向量<x1,x2,…xn>，xi是投給項(xiàng)目i的錢(qián)數(shù)，i=1,2,…,n
??目標(biāo)函數(shù)max{f1(x1)+f2(x2)+…+fn(xn)}。
??約束條件x1+x2+…+xn=m，xi∈N。
7.1 實(shí)例
??5萬(wàn)元錢(qián)，4個(gè)項(xiàng)目，效益函數(shù)如下表所示
7.2 子問(wèn)題界定和計(jì)算順序
??子問(wèn)題界定：由參數(shù)k和x界定。
??k:考慮對(duì)項(xiàng)目1,2,…,k的投資
??x:投資總錢(qián)數(shù)不超過(guò)x
??原始輸入：k=n,x=m
??子問(wèn)題計(jì)算順序：
??k=1,2,…,n
??對(duì)于給定的k,x=1,2,…,m
7.3 優(yōu)化函數(shù)的遞推方程
??Fk(x):x元錢(qián)投給前k個(gè)項(xiàng)目的最大效益。
??多步判斷：若知道p元錢(qián)（p<=x）投給前k-1個(gè)項(xiàng)目的最大效益Fk-1§，確定x元錢(qián)投給前k個(gè)項(xiàng)目的方案。
??遞推方程和邊界條件：
??Fk(x)=max{fk(xk)+Fk-1(x-xk)} k>1。
??F1(x)=f1(x)。
7.5 k=1時(shí)實(shí)例的計(jì)算
??F1(1)=11。
??F1(2)=12。
??F1(3)=13。
??F1(4)=14。
??F1(5)=15。
7.6 k=2時(shí)的實(shí)例計(jì)算
??方案(其它,項(xiàng)目2):(0,1),(1,0)
??F2(1)=max{f2(1),f1(1)}=11
??方案:(0,2),(1,1),(2,0)
??F2(2)=max{f2(2),F1(1)+f2(1),F1(2)}=12
??方案:(0,3),(1,2),(2,1),(3,0)
??F2(3)=max{f2(3),F1(1)+f2(2), F1(2)+f2(1), F1(3)}=16
??類(lèi)似的計(jì)算
??F2(4)=21， F2(5)=26
7.7 備忘錄和解
八、0-1背包問(wèn)題
??給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問(wèn)應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?
??0-1背包問(wèn)題是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題。
??設(shè)所給0-1背包問(wèn)題的子問(wèn)題
??算法復(fù)雜度分析：
??從m(i，j)的遞歸式容易看出，算法需要O(nc)計(jì)算時(shí)間。當(dāng)背包容量c很大時(shí)，算法需要的計(jì)算時(shí)間較多。例如，當(dāng)c>2n時(shí)，算法需要Ω(n2n)計(jì)算時(shí)間。
??最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問(wèn)題的最優(yōu)值。由0-1背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式如下。
8.1 算法改進(jìn)
??由m(i,j)的遞歸式容易證明，在一般情況下，對(duì)每一個(gè)確定的i(1≤i≤n)，函數(shù)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是這一類(lèi)函數(shù)的描述特征。在一般情況下，函數(shù)m(i,j)由其全部跳躍點(diǎn)唯一確定。如圖所示。
??對(duì)每一個(gè)確定的i(1≤i≤n)，用一個(gè)表p[i]存儲(chǔ)函數(shù)m(i，j)的全部跳躍點(diǎn)。表p[i]可依計(jì)算m(i，j)的遞歸式遞歸地由表p[i+1]計(jì)算，初始時(shí)p[n+1]={(0，0)}。
8.2 一個(gè)例子
??n=3，c=6，w={4，3，2}，v={5，2，1}。
8.3 算法改進(jìn)
??函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-wi)+vi作max運(yùn)算得到的。因此，函數(shù)m(i,j)的全部跳躍點(diǎn)包含于函數(shù)m(i+1，j)的跳躍點(diǎn)集p[i+1]與函數(shù)m(i+1，j-wi)+vi的跳躍點(diǎn)集q[i+1]的并集中。易知，(s,t)?q[i+1]當(dāng)且僅當(dāng)wi?s?c且(s-wi,t-vi)?p[i+1]。因此，容易由p[i+1]確定跳躍點(diǎn)集q[i+1]如下q[i+1]=p[i+1]?(wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))?p[i+1]}
??另一方面，設(shè)(a，b)和(c，d)是p[i+1]?q[i+1]中的2個(gè)跳躍點(diǎn)，則當(dāng)c?a且d<b時(shí)，(c，d)受控于(a，b)，從而(c，d)不是p[i]中的跳躍點(diǎn)。除受控跳躍點(diǎn)外，p[i+1]?q[i+1]中的其它跳躍點(diǎn)均為p[i]中的跳躍點(diǎn)。
??由此可見(jiàn)，在遞歸地由表p[i+1]計(jì)算表p[i]時(shí)，可先由p[i+1]計(jì)算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳躍點(diǎn)得到表p[i]。
8.4 一個(gè)例子
??n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。
??初始時(shí)p[6]={(0,0)}，(w5,v5)=(4,6)。因此，q[6]=p[6]?(w5,v5)={(4,6)}。p[5]={(0,0),(4,6)}。q[5]=p[5]?(w4,v4)={(5,4),(9,10)}。
??從跳躍點(diǎn)集p[5]與q[5]的并集p[5]?q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳躍點(diǎn)(5,4)受控于跳躍點(diǎn)(4,6)。將受控跳躍點(diǎn)(5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)}。
??q[4]=p[4]?(6，5)={(6，5)，(10，11)}
??p[3]={(0，0)，(4，6)，(9，10)，(10，11)}
??q[3]=p[3]?(2，3)={(2，3)，(6，9)}
??p[2]={(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)}
??q[2]=p[2]?(2，6)={(2，6)，(4，9)，(6，12)，(8，15)}
??p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}
??p[1]的最后的那個(gè)跳躍點(diǎn)(8,15)給出所求的最優(yōu)值為m(1,c)=15。
8.5 算法復(fù)雜度分析
??上述算法的主要計(jì)算量在于計(jì)算跳躍點(diǎn)集pi。由于q[i+1]=p[i+1]?(wi，vi)，故計(jì)算q[i+1]需要O(|p[i+1]|)計(jì)算時(shí)間。合并p[i+1]和q[i+1]并清除受控跳躍點(diǎn)也需要O(|p[i+1]|)計(jì)算時(shí)間。從跳躍點(diǎn)集p[i]的定義可以看出，p[i]中的跳躍點(diǎn)相應(yīng)于xi,…,xn的0/1賦值。
??因此，p[i]中跳躍點(diǎn)個(gè)數(shù)不超過(guò)2n-i+1。由此可見(jiàn)，算法計(jì)算跳躍點(diǎn)集p[i]所花費(fèi)的計(jì)算時(shí)間為
??從而，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為O(2n)。當(dāng)所給物品的重量wi(1≤i≤n)是整數(shù)時(shí)，|p[i]|≤c+1，(1≤i≤n)。在這種情況下，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為O(min{nc,2n})。
九、最優(yōu)二叉搜索樹(shù)
9.1 二叉搜索樹(shù)
??（1）若它的左子樹(shù)不空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；
??（2）若它的右子樹(shù)不空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
??（3）它的左、右子樹(shù)也分別為二叉排序樹(shù)在隨機(jī)的情況下，二叉查找樹(shù)的平均查找長(zhǎng)度和logn是等數(shù)量級(jí)的。
9.2 二叉搜索樹(shù)的期望耗費(fèi)
??搜索成功與不成功的概率：
??二叉搜索樹(shù)的期望耗費(fèi)：
??有 個(gè)節(jié)點(diǎn)的二叉樹(shù)的個(gè)數(shù)為：窮舉搜索法的時(shí)間復(fù)雜度為指數(shù)級(jí)：
9.3 二叉搜索樹(shù)的期望耗費(fèi)示例
9.4 最優(yōu)二叉搜索樹(shù)
??最優(yōu)二叉搜索樹(shù)Tij的平均路長(zhǎng)為pij，則所求的最優(yōu)值為p1,n。由 最優(yōu)二叉搜索樹(shù)問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì) 可建立計(jì)算pij的遞歸式如下
??記wi,jpi,j為m(i,j)，則m(1,n)=w1,np1,n=p1,n為所求的最優(yōu)值。計(jì)算m(i,j)的遞歸式為
??注意到，
??可以得到O(n2)的算法。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-713256.html
十、小結(jié)
??動(dòng)態(tài)規(guī)劃算法和分治法的相同點(diǎn)是什么？
??動(dòng)態(tài)規(guī)劃算法和分治法的不同之處在哪里？
??用“表”記錄所有已有子問(wèn)題的答案！避免重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間復(fù)雜度。
??動(dòng)態(tài)規(guī)劃通常用來(lái)計(jì)算“最優(yōu)”解，不適合計(jì)算“合并”解。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-713256.html
到了這里，關(guān)于【算法分析與設(shè)計(jì)】動(dòng)態(tài)規(guī)劃（下）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
