摘抄：http://www.cnblogs.com/Anker/archive/2013/05/04/3059070.html

1. 0-1背包問題描述

有一個竊賊在偷竊一家商店時發(fā)現(xiàn)有n件物品，第i件物品價值為vi元，重量為wi，假設(shè)vi和wi都為整數(shù)。他希望帶走的東西越值錢越好，但他的背包中之多只能裝下W磅的東西，W為一整數(shù)。他應(yīng)該帶走哪幾樣?xùn)|西？

0-1背包問題中：每件物品或被帶走，或被留下，（需要做出0-1選擇）。小偷不能只帶走某個物品的一部分或帶走兩次以上同一個物品。

    wi  vi  
a   2   6   
b   2   3   
c   6   5   
d   5   4   
e   4   6   

w       1   2   3   4   5   6   7   8   9   10
a       0   6   6   9   9   12  12  15  15  15
b       0   3   3   6   6   9   9   9   10  11
c       0   0   0   6   6   6   6   6   10  11
d       0   0   0   6   6   6   6   6   10  10
e       0   0   0   6   6   6   6   6   6   6

這張表是至底向上，從左到右生成的。(a，b，c，d，e五件商品，最多能裝10磅的東西，w行表重量，其他行的數(shù)字表max價值)

2. 0-1背包問題子結(jié)構(gòu)：

選擇一個給定物品i，則需要比較選擇i的形成的子問題的最優(yōu)解與不選擇i的子問題的最優(yōu)解。分成兩個子問題，進(jìn)行選擇比較，選擇最優(yōu)的。

3. 偽代碼：

4. 編程實(shí)現(xiàn)

#include <iostream>
using namespace std;

//物品數(shù)據(jù)結(jié)構(gòu)
typedef struct commodity
{
    int value;  //價值
    int weight; //重量
}commodity;

const int N = 3;  //物品個數(shù)
const int W = 50; //背包的容量

//初始物品信息
commodity goods[N+1]={{0,0},{60,10},{100,20},{120,30}};
int select[N+1][W+1];

int max_value();

int main()
{
    int maxvalue = max_value();
    cout<<"The max value is: ";
    cout<<maxvalue<<endl;
    int remainspace = W;
    //輸出所選擇的物品列表：
    for(int i=N; i>=1; i--)
    {
        if (remainspace >= goods[i].weight)
        {
             if ((select[i][remainspace]-select[i-1][remainspace-goods[i].weight]==goods[i].value))
             {
                 cout << "item " << i << " is selected!" << endl;
                 remainspace = remainspace - goods[i].weight;//如果第i個物品被選擇，那么背包剩余容量將減去第i個物品的重量 ;
             }
        }
    }
    return 0;
}
int max_value()
{
    //初始沒有物品時候，背包的價值為0
    for(int w=1;w<=W;++w)
        select[0][w] = 0;
    for(int i=1;i<=N;++i)
    {
        select[i][0] = 0;  //背包容量為0時，最大價值為0
           for(int w=1;w<=W;++w)
           {
               if(goods[i].weight <= w)  //當(dāng)前物品i的重量小于等于w，進(jìn)行選擇
               {
                   if( (goods[i].value + select[i-1][w-goods[i].weight]) > select[i-1][w])
                    select[i][w] = goods[i].value + select[i-1][w-goods[i].weight];
                   else
                    select[i][w] = select[i-1][w];
               }
               else //當(dāng)前物品i的重量大于w，不選擇
                 select[i][w] = select[i-1][w];
           }
    }
    return select[N][W];  //最終求得最大值
}

5. 測試結(jié)果

image.png