動態(tài)規(guī)劃簡介

動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題琼了，先求解子問題逻锐，然后從這些子問題的解得到原問題的解。與分治法不同的是雕薪，適合于動態(tài)規(guī)劃算法求解的問題昧诱，經(jīng)分解的得到的子問題往往不是相互獨(dú)立的。分治算法兩個自問題一般是不重疊的所袁。
??若用分治法來解這類問題盏档，則分解的得到的子問題數(shù)目太多，以至于最后解決原問題需要耗費(fèi)指數(shù)時間燥爷。在用分治法求解時蜈亩，有些子問題被重復(fù)計算了許多次。如果我們能夠保存已解決子問題的答案前翎，而在需要時再找出已求得的答案稚配，這樣就可以避免大量的重復(fù)計算。

自頂向下計算會產(chǎn)生重復(fù)計算的問題港华。比如要計算下圖中要計算a[i,j]為塔頂?shù)淖铀塬@得的最大路徑和道川。那么每走一層都要問下一層它走過最長的路徑是啥，紅框部分重疊就是為重復(fù)部分立宜，那么這部分就被至少問了2次以上愤惰。

動態(tài)規(guī)劃應(yīng)用

1. 計算最長公共子序列長度
??計算最長公共子序列長度的動態(tài)規(guī)劃算法LCSLength以序列X={x1,x2,...,xm}和Y={y1,y2,...,yn}作為輸入，計算得到數(shù)組c赘理，其中c[i][j]存儲序列Xi={x1,x2,...,xi}和序列Yj={y1,y2,...,yj}的最長公共子序列長度宦言。

解題思路
??設(shè)A="a[0]...a[m]"，B="b[0]...b[n]"商模，并且Z="z[0]...z[k]"為它們最長公共子序列奠旺。在找A、B公共子序列時施流，若a[m]=b[n]响疚，則進(jìn)一步解決一個子問題：找"a[0]...a[m-1]"和"b[0]...b[n-1]"的最長公共子序列。若a[m]≠b[n]瞪醋，則要解決兩個子問題：找"a[0]...a[m-1]"和"b[0]...b[n]"的最長公共子序列和找"a[0]...a[m]"和"b[0]...b[n-1]"的最長公共子序列忿晕，再取兩者中較長者作為A和B的最長公共子序列。
??但LCSLength存在子問題重疊性質(zhì)银受，如在計算X和Y的LCSLength時践盼，可能要計算X和Y[n-1]及X[m-1]和Y的LCSLength鸦采，而這兩個子問題都包含了一個公共子問題，即計算X[m-1]和Y[n-1]的最長公共子序列咕幻。所以用c[i][j]記錄Xi和Yj的最長公共子序列的長度渔伯。當(dāng)i=0或j=0時，空序列時Xi和Yj的最長公共子序列肄程。故此時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++)          //自底向上計算
       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]; }
       }
}

時間復(fù)雜度
??由于每個數(shù)組單元的計算耗時為O(1)時間，算法LCSLength耗時O(mn)蓝厌。

2. 0-1背包問題
??0-1背包問題：給定n種物品和一背包玄叠。物品i的重量是wi，其價值為vi拓提，背包的容量為C读恃。問應(yīng)該如何選擇裝入背包中的物品，使得裝入背包中的物品的總價值最大崎苗？
??選擇裝入背包的物品時，對每種物品i只有兩種選擇舀寓，即裝入背包或不裝入背包胆数。不能將物品i裝入背包多次，也不能只裝入部分的物品i互墓。因此必尼，該問題成為0-1背包問題。

最優(yōu)子結(jié)構(gòu)性質(zhì)
??此問題的形式化描述是：給定C>0篡撵，wi>0判莉，vi>0，1<=i<=n育谬，要求找出一個n元0-1向量(x1券盅，x2，...膛檀，xn)锰镀，xi∈{0，1}咖刃，1<=i<=n泳炉，使得∑(i=1_{n)wixi<=C，而且∑(i=1}n)vixi達(dá)到最大嚎杨。

解題思路
??有編號分別為a,b,c,d,e的五件物品，它們的重量分別是2,2,6,5,4锻狗，它們的價值分別是6,3,5,4,6满力，現(xiàn)在給你個承重為10的背包，如何讓背包里裝入的物品具有最大的價值總和轻纪？

代碼
??當(dāng)wi（1<=i<=n）為正整數(shù)時拍摇，用二維數(shù)組m[][]來存儲m(i,j)的相應(yīng)值亮钦，可設(shè)計解0-1背包問題的動態(tài)規(guī)劃算法 Knapsack如下：

//n為物品個數(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)前物品重量時m[n][j]的值（若背包容量<當(dāng)前物品則保留為0）
   for(int j=w[n]; j<=c; j++)  m[n][j] = v[n];

   /**計算下標(biāo)比n小的**/
   for(int i = n-1; i>1 ; i--){
     jMax = min(w[i]-1,c);
     //沒選之前授翻，m[i][j]皆為前面選的價值總和
     for(int j=0; j<=jMax; j++)  m[i][j] = m[i+1][j];
     //j從放得下本物品開始的容量開始
     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計算后或悲，m[1][c]給出所要求的0-1背包問題的最優(yōu)值孙咪。相應(yīng)的最優(yōu)解可由算法Traceback計算如下堪唐。如果m[1][c]=m[2][c]，則x1=0翎蹈，否則x1=1淮菠。當(dāng)x1=0時，由m[2][c]繼續(xù)構(gòu)造最優(yōu)解荤堪。