0-1背包问题

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

1. 0-1背包问题描述

有一个窃贼在偷窃一家商店时发现有n件物品，第i件物品价值为vi元，重量为wi，假设vi和wi都为整数。他希望带走的东西越值钱越好，但他的背包中之多只能装下W磅的东西，W为一整数。他应该带走哪几样东西？

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行表重量，其他行的数字表max价值)

2. 0-1背包问题子结构：

选择一个给定物品i，则需要比较选择i的形成的子问题的最优解与不选择i的子问题的最优解。分成两个子问题，进行选择比较，选择最优的。

0-1背包问题递归过程：设有n个物品，背包的重量为w，C[i][w]为最优解。即：

3. 伪代码：

4. 编程实现

#include <iostream>
using namespace std;

//物品数据结构
typedef struct commodity
{
    int value;  //价值
    int weight; //重量
}commodity;

const int N = 3;  //物品个数
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)  //当前物品i的重量小于等于w，进行选择
               {
                   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 //当前物品i的重量大于w，不选择
                 select[i][w] = select[i-1][w];
           }
    }
    return select[N][W];  //最终求得最大值
}

5. 测试结果

image.png