前言

背包問題是一個經(jīng)典的算法問題，可以用動態(tài)規(guī)劃，貪心法，分支界限法等方法解決

問題描述：有n個物品，編號1,2,3，、、n，其中第 i 個物品重量為Wi 價值 Vi ，有一個容量為W的背包。

在容量允許范圍內(nèi)，如何選擇物品，可以得到最大的價值。（為了簡單起見，假設(shè)物品的重量 Wi 和價值Vi 都是正數(shù)）

根據(jù)取物品的方式，背包問題又可以被分為三類：

0/1背包問題(0-1 knapsack problem)

這也是最常見的背包問題，對于每個物品，要么取走要么不取走，每個物品只能取一次。

可以用數(shù)學(xué)表達(dá)式表示為：

• maximize   
• subject to  

有界限的背包問題(bounded knapsack problem)

對應(yīng)于上文，每個物品最多可以取Gi次.也可以不取。用數(shù)學(xué)表達(dá)式描述為：

• maximize 
• subject to 

注意看xi取值范圍。其中的“界限”說的是取的次數(shù)上限

無界限背包( unbounded knapsack problem (UKP))

相應(yīng)的，無界限背包說的就是每個物品取的次數(shù)無限了，也就是上文中的xi 可以為任意的正整數(shù)。

今天主要說的是0、1背包問題，解法是動態(tài)規(guī)劃。當(dāng)然，對于另外兩種問題也會有所介紹。

問題分析：

用動態(tài)規(guī)劃解問題首先要有效的找出子問題，可以通過這個子問題得推得原問題的解，通常子問題的實質(zhì)是和原問題相同的，只是規(guī)模上的縮小，

也就是說子問題和原問題可以有相同的表示形式，問題可通過不斷的縮小規(guī)模（一般都會有一個界限）能找到子問題的解。

這個問題要求解的是能用背包帶走的物品的最大價值。定義 m[i,w] 為：

用第1,、2、3、、i 個物品裝入質(zhì)量<=W的背包的最大價值。

m[i,w]的取值情況分析：

1）  ，背包的質(zhì)量為w，里面沒有物品，所以它的價值為0；

2）   ，背包質(zhì)量為0，所以里面沒法裝任何東西， 不論前面的 i 是多少，總價值為0；

對于任意的第 i  個物品，有兩種情況，放進(jìn)背包或者不放。

不要第 i  個物品 如果 則：

3）    因為第i 個物品的重量大于背包的容量，所以不可放入。

如果. 那么

4）  

對于第 i 個物品，有兩種可選擇方案：如果放入背包中，那么 m[i,w]=m[i-1,w-wi]+vi　也就是 i 的前一個的最大值加上自己的價值。

如果不要第 i 個物品，那么：m[i,w]=m[i-1,w]。也就是 i 的前一個的最大值。

因為背包問題最后要取得最大的價值，所以就選這兩種情況中價值最大的。

在這個問題中，定義子問題： m[i,w] 對于每個子問題，都可通過上面的分析求出。通過3），4）可以發(fā)現(xiàn)，每一次求取子問題，問題的規(guī)模就被縮小。

要么在w 上減小，要么在 i 上減小。最后問題的規(guī)模會被縮小為 m[i,0]和m[0,w].而這兩個的值都為0，只要逆向思維反推回去，就能逐步得到問題的解。

算法描述

附c++代碼：

 c-free 5編譯通過

View Code

/*0、1背包問題
一條魚@博客園 
http://www.rzrgm.cn/yanlingyin/ 
2011-12-25 
*/


#include <iostream>
#include<fstream>
#include<algorithm>
#include<vector>

//存儲元素的結(jié)構(gòu) 
typedef struct item
{
    int weight;
    int values;
}item;



using namespace std;
int main()
{
    int weight=10;
    int itemnum=4;
    //int k[10][4];
    
     
    vector<vector<int> > k(11,vector<int>(5));
    item items[4]={{6,30},{3,14},{4,16},{2,9}};

    
    for(int w=0;w<=weight;w++)
    {
        for(int j=0;j<=itemnum;j++)
        {
            k[w][j]=0;    
        }
    
    }

    //輸出數(shù)組    
    for(int i=0;i<=weight;i++)
    {
        for(int j=0;j<=itemnum;j++)
        {
            cout<<k[i][j];
        }
        cout<<"\n";
    }
    
    
    for(int w=1;w<=weight;w++)
    {
        cout<<"測試\n";  
        for(int j=1;j<=itemnum;j++)
        {
            if(items[j-1].weight>w)        //物品質(zhì)量大于背包容量，舍去 
            {
                k[w][j]=k[w][j-1];
            }
            else        //對于兩種情況選出較大值 
            {
                k[w][j]=max(k[w][j-1],(k[w-items[j-1].weight][j-1]+items[j-1].values));
            }
            cout<<"k["<<w<<"]["<<j<<"]="<<k[w][j]<<"\n";
            
        }
        
    }
    
    cout<<"輸出哦了"<<k[weight][itemnum]<<"\n";
    
    for(int i=0;i<=weight;i++)
    {
        for(int j=0;j<=itemnum;j++)
        {
            cout<<k[i][j]<<" ";
        }
        cout<<"\n";
    }
    
}

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

動態(tài)規(guī)劃通常用于最優(yōu)化問題，此類問題可能有很多可行解，每一個解有一個值，而我們希望找出一個具有最優(yōu)值的解，

動態(tài)規(guī)劃算法設(shè)計可分為如下步驟：

1）描述最優(yōu)解的結(jié)構(gòu)

2）遞歸定義最優(yōu)解的值

3）按底向上的方式計算最優(yōu)解的值

4）由計算出的結(jié)果構(gòu)造一個最優(yōu)解

動態(tài)規(guī)劃的第一步是描述最優(yōu)解的結(jié)構(gòu)，如果問題的一個最優(yōu)解中包含了子問題的最優(yōu)解，該問題具有最優(yōu)解結(jié)構(gòu)。當(dāng)一個子問題

有最優(yōu)解結(jié)構(gòu)時，提示我們動態(tài)規(guī)劃適用。如本例中的m[i,w]就是一個子問題，里面包含了另一個子問題的最優(yōu)解：

m[i-1,w],m[i-1,w-1]。解題的過程中把結(jié)果記錄在數(shù)組中，后面的解更具前面的解得出，最后找到問題的解。

參考資料： 

http://en.wikipedia.org/wiki/Knapsack_problem

http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf

《算法導(dǎo)論》

歡迎轉(zhuǎn)載，請注明出處：http://www.rzrgm.cn/yanlingyin/

一條魚@博客園

2011-12-25