动态规划 之 0-1背包问题

2022-08-21 09:27:39

关于背包问题，其实可以分为两种类型：0-1背包问题 和部分背包问题。

1、先通过一个例子来说明一下二者的区别吧！

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

0-1背包问题：每件物品或被带走，或被留下，（需要做出0-1选择）。小偷不能只带走某个物品的一部分或带走两次以上同一个物品。

部分背包问题：小偷可以只带走某个物品的一部分，不必做出0-1选择。

更通俗点理解，0-1背包问题的一件物品可以想象成是一个金锭；而部分背包问题中的一件物品可以想象成是金粉。


2、这两个问题的解决策略也是不同的。

关于0-1背包问题，采用的是动态规划的解决方法；而部分背包问题采用的是贪心法。

0-1背包问题：

在选择是否要把一个物品加到背包中，必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较。这种方式形成的问题导致了许多重叠子问题，满足动态规划的特征。


部分背包问题：

总是选择每一磅价值 (Vi / Wi) 最大的物品添加进背包中。那么其解决过程是：对每磅价值进行排序，依次从大到小选择添加进背包中。


3、下面对于0-1背包问题的解决过程进行讨论和进行代码实现。

（1）动态规划解决0-1背包问题步骤如下：

0-1背包问题子结构：选择一个给定物品i，则需要比较  选择 i 的形成的子问题的最优解与 不选择 i 的子问题的最优解。分成两个子问题，进行选择比较，选择最优的。

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


（2）下面给出伪代码实现：



（3）编程实现

#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];  //最终求得最大值
}

（4）程序运行结果：



（5）给出一种简约点的实现。

通过上面的伪代码，我们会发现，实现的过程有点罗嗦，下面给出一个简约点的实现，思路都是一样的。


①伪代码：



②编程实现（注意其他的变量都同上面代码一样，这里只是给出求解过程的函数代码）：

//获取两个数的大者
int getMax(int a,int b)
{
    return a>=b?a:b;
}
int Backpack()
{
    //初始化二维表中的第一行
    for(int k=0; k<=W; k++) select[0][k] = 0;
    //初始化二维表中的第一列
    for(int k=0; k<=N; k++) select[k][0] = 0;

    //逐行进行填表
    for(int i=1; i<=N; i++) //物品编号从 1~N
    {
        for(int j=1; j<=W; j++) //背包容量从 1~W
        {
            select[i][j] = select[i-1][j];
            if(goods[i].weight <= j)
            {
                select[i][j] = getMax(select[i][j],select[i-1][j-goods[i].weight]+goods[i].value);
            }
        }
    }
    return select[N][W];
}

相比较而言是不是简约好多了呢!吐舌头


（6）再来看看其中最优值和最优解的求解过程。

最优值：求解整个背包最后的总价值达到最优。求解背包问题的最优值，关键是要弄清楚上面的递推式子。


最优解：当背包价值达到最大时，列出所选取的物品都是那些。

代码的实现过程是这样的：

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个物品的重量 ;
             }
        }
    }

简单分析一下，其实这是一个反向推导出最优解的过程。那么当然输出的物品编号也就是倒序的了，可以用一个栈保存下来，然后再输出就可以了，这个问题不大。


文章参考：http://www.cnblogs.com/Anker/archive/2013/05/04/3059070.html


  • 作者：Crayondeng
  • 原文链接：https://blog.csdn.net/Crayon_DyS/article/details/15784093
    更新时间：2022-08-21 09:27:39