動(dòng)態(tài)規(guī)劃簡(jiǎn)介
動(dòng)態(tài)規(guī)劃算法與分治法類(lèi)似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治法不同的是，適合于動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題，經(jīng)分解的得到的子問(wèn)題往往不是相互獨(dú)立的。分治算法兩個(gè)自問(wèn)題一般是不重疊的。
??若用分治法來(lái)解這類(lèi)問(wèn)題，則分解的得到的子問(wèn)題數(shù)目太多，以至于最后解決原問(wèn)題需要耗費(fèi)指數(shù)時(shí)間。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。如果我們能夠保存已解決子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算。
自頂向下計(jì)算會(huì)產(chǎn)生重復(fù)計(jì)算的問(wèn)題。比如要計(jì)算下圖中要計(jì)算a[i,j]為塔頂?shù)淖铀塬@得的最大路徑和。那么每走一層都要問(wèn)下一層它走過(guò)最長(zhǎng)的路徑是啥，紅框部分重疊就是為重復(fù)部分，那么這部分就被至少問(wèn)了2次以上。
動(dòng)態(tài)規(guī)劃應(yīng)用
1. 計(jì)算最長(zhǎng)公共子序列長(zhǎng)度
??計(jì)算最長(zhǎng)公共子序列長(zhǎng)度的動(dòng)態(tài)規(guī)劃算法LCSLength以序列X={x1,x2,...,xm}和Y={y1,y2,...,yn}作為輸入，計(jì)算得到數(shù)組c，其中c[i][j]存儲(chǔ)序列Xi={x1,x2,...,xi}和序列Yj={y1,y2,...,yj}的最長(zhǎng)公共子序列長(zhǎng)度。
解題思路
??設(shè)A="a[0]...a[m]"，B="b[0]...b[n]"，并且Z="z[0]...z[k]"為它們最長(zhǎng)公共子序列。在找A、B公共子序列時(shí)，若a[m]=b[n]，則進(jìn)一步解決一個(gè)子問(wèn)題：找"a[0]...a[m-1]"和"b[0]...b[n-1]"的最長(zhǎng)公共子序列。若a[m]≠b[n]，則要解決兩個(gè)子問(wèn)題：找"a[0]...a[m-1]"和"b[0]...b[n]"的最長(zhǎng)公共子序列和找"a[0]...a[m]"和"b[0]...b[n-1]"的最長(zhǎng)公共子序列，再取兩者中較長(zhǎng)者作為A和B的最長(zhǎng)公共子序列。
??但LCSLength存在子問(wèn)題重疊性質(zhì)，如在計(jì)算X和Y的LCSLength時(shí)，可能要計(jì)算X和Y[n-1]及X[m-1]和Y的LCSLength，而這兩個(gè)子問(wèn)題都包含了一個(gè)公共子問(wèn)題，即計(jì)算X[m-1]和Y[n-1]的最長(zhǎng)公共子序列。所以用c[i][j]記錄Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。當(dāng)i=0或j=0時(shí)，空序列時(shí)Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)c[i][j]=0.其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：
代碼
void LSCLength(int m,int n,char *x,char *y,int **c){
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++) //自底向上計(jì)算
for(j=1;j<=n;i++)
{
if(x[i]==y[j]) { c[i][j] = c[i-1][j-1]+1; }
else if(c[i-1][j] >= c[i][j-1]) c[i][j]=c[i-1][j]
else { c[i][j]=c[i][j-1]; }
}
}
時(shí)間復(fù)雜度
??由于每個(gè)數(shù)組單元的計(jì)算耗時(shí)為O(1)時(shí)間，算法LCSLength耗時(shí)O(mn)。
2. 0-1背包問(wèn)題
??0-1背包問(wèn)題：給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問(wèn)應(yīng)該如何選擇裝入背包中的物品，使得裝入背包中的物品的總價(jià)值最大？
??選擇裝入背包的物品時(shí)，對(duì)每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。因此，該問(wèn)題成為0-1背包問(wèn)題。
最優(yōu)子結(jié)構(gòu)性質(zhì)
??此問(wèn)題的形式化描述是：給定C>0，wi>0，vi>0，1<=i<=n，要求找出一個(gè)n元0-1向量(x1，x2，...，xn)，xi∈{0，1}，1<=i<=n，使得∑(i=1n)wixi<=C，而且∑(i=1n)vixi達(dá)到最大。
??設(shè)(y1,y2,…,yn)是 (3.4.1)的一個(gè)最優(yōu)解.則(y2,…,yn)是下面相應(yīng)子問(wèn)題的一個(gè)最優(yōu)解：
證明：使用反證法。若不然，設(shè)(z2,z3,…,zn)是上述子問(wèn)題的一個(gè)最優(yōu)解，而(y2,y3,…,yn)不是它的最優(yōu)解。顯然有
???????????∑vizi > ∑viyi (i=2,…,n)
??且????????w1y1+ ∑wizi<= c
??因此????v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n)
說(shuō)明(y1,z2, z3,…,zn)是(3.4.1)0-1背包問(wèn)題的一個(gè)更優(yōu)解——>導(dǎo)出(y1,y2,…,yn)不是背包問(wèn)題的最優(yōu)解（因?yàn)榇笄疤嵋呀?jīng)是(y1,y2,…,yn)是 (3.4.1)的一個(gè)最優(yōu)解，而現(xiàn)在又導(dǎo)出一個(gè)(y1,z2, z3,…,zn)是(3.4.1)的最優(yōu)解，所以是前后矛盾的），矛盾。
解題思路
??有編號(hào)分別為a,b,c,d,e的五件物品，它們的重量分別是2,2,6,5,4，它們的價(jià)值分別是6,3,5,4,6，現(xiàn)在給你個(gè)承重為10的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和？
首先要明確這張表是至底向上，從左到右生成的。為了敘述方便，用e2單元格表示e行2列的單元格，這個(gè)單元格的意義是用來(lái)表示只有物品e時(shí)，有個(gè)承重為2的背包，那么這個(gè)背包的最大價(jià)值是0，因?yàn)閑物品的重量是4，背包裝不了。對(duì)于d2單元格，表示只有物品e，d時(shí),承重為2的背包,所能裝入的最大價(jià)值，仍然是0，因?yàn)槲锲積,d都不是這個(gè)背包能裝的。
??同理，c2=0，b2=3,a2=6。對(duì)于承重為8的背包，a8=15,是怎么得出的呢？根據(jù)01背包的狀態(tài)轉(zhuǎn)換方程，需要考察兩個(gè)值，一個(gè)是f[i-1,j],對(duì)于這個(gè)例子來(lái)說(shuō)就是b8的值9，另一個(gè)是f[i-1,j-Wi]+Pi。
??在這里， f[i-1,j]表示我有一個(gè)承重為8的背包，當(dāng)只有物品b,c,d,e四件可選時(shí)，這個(gè)背包能裝入的最大價(jià)值。f[i-1,j-Wi]表示我有一個(gè)承重為6的背包（等于當(dāng)前背包承重減去物品a的重量），當(dāng)只有物品b,c,d,e四件可選時(shí)，這個(gè)背包能裝入的最大價(jià)值。f[i-1,j-Wi]就是指單元格b6,值為9，Pi指的是a物品的價(jià)值，即6。由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9，所以物品a應(yīng)該放入承重為8的背包。
??設(shè)所給0-1背包問(wèn)題的子問(wèn)題的最優(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)的遞歸式如下：
在max{m(i+1,j),m(i+1,j-wi)+vi}中，m(i+1,j)代表不選當(dāng)前物品，而m(i+1,j-wi)+vi代表選擇當(dāng)前物品（加上當(dāng)前物品價(jià)值）。如果當(dāng)前物品重量比背包總?cè)萘窟€打的話(huà)，那就只能是m(i+1,j)。
代碼
??當(dāng)wi（1<=i<=n）為正整數(shù)時(shí)，用二維數(shù)組m[][]來(lái)存儲(chǔ)m(i,j)的相應(yīng)值，可設(shè)計(jì)解0-1背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法 Knapsack如下：
//n為物品個(gè)數(shù)，c為背包容量
void Knapsack(Type v, int w , int c , int n , Type **m)
{
int jMax = min(w[n]-1,c); //比較背包容量和當(dāng)前物品的重量
/**先初始化下標(biāo)最大（n）的**/
//初始化背包容量從0到j(luò)Max的最優(yōu)值
for(int j=0; j<=jMax; j++) m[n][j] = 0;
//初始化背包容量>=當(dāng)前物品重量時(shí)m[n][j]的值（若背包容量<當(dāng)前物品則保留為0）
for(int j=w[n]; j<=c; j++) m[n][j] = v[n];
/**計(jì)算下標(biāo)比n小的**/
for(int i = n-1; i>1 ; i--){
jMax = min(w[i]-1,c);
//沒(méi)選之前，m[i][j]皆為前面選的價(jià)值總和
for(int j=0; j<=jMax; j++) m[i][j] = m[i+1][j];
//j從放得下本物品開(kāi)始的容量開(kāi)始
for(int j=w[i]; j<=c; j++) m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
m[1][c] = m[2][c];
if(c>=w[1]) m[1][c] = max(m[1][c],m[2][c-w[1]]+v[1]);
}
//構(gòu)造相應(yīng)的最優(yōu)解
void Traceback(Type **m, int w , int c, int n, int x)
{
for(int i=1;i<=n;i++)
if(m[i][c]==m[i+1][c]) x[i] = 0;
else { x[i] = 1;c-=w[i]; }
x[n] = (m[n][c])?1:0;
}
算法Knapsack計(jì)算后，m[1][c]給出所要求的0-1背包問(wèn)題的最優(yōu)值。相應(yīng)的最優(yōu)解可由算法Traceback計(jì)算如下。如果m[1][c]=m[2][c]，則x1=0，否則x1=1。當(dāng)x1=0時(shí)，由m[2][c]繼續(xù)構(gòu)造最優(yōu)解。
