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

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

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

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

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

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

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

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

我們以01背包為例子：

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

表達(dá)式中各個符號的具體含義。

w[i] : 第i個物體的重量；

p[i] : 第i個物體的價值；

c[i][m] ：前i個物體放入容量為m的背包的最大價值；

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

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

由此可得：

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

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

問題分析：令V(i,j)表示在前i(1<=i<=n)個物品中能夠裝入容量為就j(1<=j<=C)的背包中的物品的最大價值，則可以得到如下的動態(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個物品的重量大于背包的容量，則裝人前i個物品得到的最大價值和裝入前i-1個物品得到的最大價是相同的，即物品i不能裝入背包；第(2)個式子表明:如果第i個物品的重量小于背包的容量，則會有一下兩種情況：(a)如果把第i個物品裝入背包，則背包物品的價值等于第i-1個物品裝入容量位j-wi 的背包中的價值加上第i個物品的價值vi; (b)如果第i個物品沒有裝入背包，則背包中物品價值就等于把前i-1個物品裝入容量為j的背包中所取得的價值。顯然，取二者中價值最大的作為把前i個物品裝入容量為j的背包中的最優(yōu)解。

#include<stdlib.h>
#include<stdio.h>
int V[200][200];//前i個物品裝入容量為j的背包中獲得的最大價值
int max(int a,int b)  //一個大小比較函數(shù)，用于當(dāng)總重大于第I行時 
{
   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;//獲得的最大價值
  int w[4];//物品的重量   重量  價值  和物品的狀態(tài) 均對應(yīng)著存到數(shù)組中，物品從1開始。 
  int v[4];//物品的價值
  int x[4];//物品的選取狀態(tài)   選中則是1  沒選中為0 
  int n,i;
  int C;//背包最大容量
  n=4;
  printf("請輸入背包的最大容量:\n");
  scanf("%d",&C);
  
  printf("物品數(shù):\n");
  scanf("%d",&n);
  printf("請分別輸入物品的重量:\n");
  for(i=0;i<n;i++)
    scanf("%d",&w[i]);

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

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

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

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