0-1背包问题

2017-08-15  本文已影响0人  RainingMan

摘抄: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
上一篇 下一篇

猜你喜欢

热点阅读