算法分析之動(dòng)態(tài)規(guī)劃詳解

先舉個(gè)例子01背包問題具體例子：假設(shè)現(xiàn)有容量15kg的背包，另外有4個(gè)物品，分別為a1，a2，a3, a4。物品a1重量為3kg，價(jià)值為4；物品a2重量為4kg，價(jià)值為5；物品a3重量為5kg，價(jià)值為6, a4重6千克，價(jià)值為7。將哪些物品放入背包可使得背包中的總價(jià)值最大？

對(duì)于這樣的問題，如果如上述所涉及的數(shù)據(jù)比較少的時(shí)候，我們通過列舉就能算出來，例如，上邊的例子的答案是：將a4和a3與a2放入背包中，這樣總重量為6+5+4=15，總價(jià)值為5+6+7=18，這樣總價(jià)值最大。但是如果上述給出的條件很多，此時(shí)我們光靠用眼睛看是絕對(duì)不行的，所以我們要用上動(dòng)態(tài)規(guī)劃的思想。

關(guān)于動(dòng)態(tài)規(guī)劃的思想是如何建立的，若初學(xué)者對(duì)動(dòng)態(tài)規(guī)劃還是很迷惑的，可以打開下面的文章鏈接。

點(diǎn)擊打開鏈接  http://blog.csdn.net/u014028070/article/details/39695669

動(dòng)態(tài)規(guī)劃的基本思想與分治法類似，也是將待求解的問題分解為若干個(gè)子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時(shí)，列出各種可能的局部解，通過決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個(gè)子問題就是初始問題的解。

由于動(dòng)態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個(gè)特點(diǎn)，為減少重復(fù)計(jì)算，對(duì)每一個(gè)子問題只解一次，將其不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。

與分治法最大的差別是：適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解后得到的子問題往往不是互相獨(dú)立的（即下一個(gè)子階段的求解是建立在上一個(gè)子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解）。

我們以01背包為例子：

思路：先將原始問題一般化，欲求背包能夠獲得的總價(jià)值，即欲求前i個(gè)物體放入容量為m（kg）背包的最大價(jià)值c[i][m]——使用一個(gè)數(shù)組來存儲(chǔ)最大價(jià)值。而前i個(gè)物體放入容量為m（kg）的背包，又可以轉(zhuǎn)化成前(i-1)個(gè)物體放入背包的問題。下面使用數(shù)學(xué)表達(dá)式描述它們兩者之間的具體關(guān)系。

表達(dá)式中各個(gè)符號(hào)的具體含義。

w[i] : 第i個(gè)物體的重量；

p[i] : 第i個(gè)物體的價(jià)值；

c[i][m] ：前i個(gè)物體放入容量為m的背包的最大價(jià)值；

c[i-1][m] ：前i-1個(gè)物體放入容量為m的背包的最大價(jià)值；

c[i-1][m-w[i]] ： 前i-1個(gè)物體放入容量為m-w[i]的背包的最大價(jià)值；

由此可得：

c[i][m]=max{c[i-1][m-w[i]]+pi , c[i-1][m]}（此時(shí)用到遞歸）

引用網(wǎng)上的一個(gè)圖更能說明情況：

問題分析：令V(i,j)表示在前i(1<=i<=n)個(gè)物品中能夠裝入容量為就j(1<=j<=C)的背包中的物品的最大價(jià)值，則可以得到如下的動(dòng)態(tài)規(guī)劃函數(shù):

(1)   V(i,0)=V(0,j)=0

(2)   V(i,j)=V(i-1,j)  j<wi 

V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) }j>wi

(1)式表明：如果第i個(gè)物品的重量大于背包的容量，則裝人前i個(gè)物品得到的最大價(jià)值和裝入前i-1個(gè)物品得到的最大價(jià)是相同的，即物品i不能裝入背包；第(2)個(gè)式子表明:如果第i個(gè)物品的重量小于背包的容量，則會(huì)有一下兩種情況：(a)如果把第i個(gè)物品裝入背包，則背包物品的價(jià)值等于第i-1個(gè)物品裝入容量位j-wi 的背包中的價(jià)值加上第i個(gè)物品的價(jià)值vi; (b)如果第i個(gè)物品沒有裝入背包，則背包中物品價(jià)值就等于把前i-1個(gè)物品裝入容量為j的背包中所取得的價(jià)值。顯然，取二者中價(jià)值最大的作為把前i個(gè)物品裝入容量為j的背包中的最優(yōu)解。

#include<stdlib.h>
#include<stdio.h>
int V[200][200];//前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值
int max(int a,int b)  //一個(gè)大小比較函數(shù)，用于當(dāng)總重大于第I行時(shí) 
{
   if(a>=b)
     return a;
   else return b;
}

int Knap(int n,int w[],int v[],int x[],int C)
{
  int i,j;
  for(i=0;i<=n;i++)
    V[i][0]=0;
  for(j=0;j<=C;j++)
    V[0][j]=0;
  for(i=0;i<=n-1;i++)
    for(j=0;j<=C;j++)
      if(j<w[i])
        V[i][j]=V[i-1][j];
      else
        V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);
      j=C;
      for(i=n-1;i>=0;i--)
      {
        if(V[i][j]>V[i-1][j])
        {
        x[i]=1;
        j=j-w[i];
        }
      else
        x[i]=0;   
      }
      printf("選中的物品是:\n");
      for(i=0;i<n;i++)
        printf("%d ",x[i]);
      printf("\n");
    return V[n-1][C];
    
}

int main()
{
  int s;//獲得的最大價(jià)值
  int w[4];//物品的重量   重量  價(jià)值  和物品的狀態(tài) 均對(duì)應(yīng)著存到數(shù)組中，物品從1開始。 
  int v[4];//物品的價(jià)值
  int x[4];//物品的選取狀態(tài)   選中則是1  沒選中為0 
  int n,i;
  int C;//背包最大容量
  n=4;
  printf("請(qǐng)輸入背包的最大容量:\n");
  scanf("%d",&C);
  
  printf("物品數(shù):\n");
  scanf("%d",&n);
  printf("請(qǐng)分別輸入物品的重量:\n");
  for(i=0;i<n;i++)
    scanf("%d",&w[i]);

  printf("請(qǐng)分別輸入物品的價(jià)值:\n");
  for(i=0;i<n;i++)
    scanf("%d",&v[i]);

  s=Knap(n,w,v,x,C);  //調(diào)用核心函數(shù) 

  printf("最大物品價(jià)值為:\n");
  printf("%d\n",s);
  system("pause");
  return 0;
   
  
}

暫時(shí)就理解這么多，還在不斷學(xué)習(xí)中。