动态规划算法（Dynamic Programming）之0-1背包问题

Michael阿明

发布于 2021-02-20 10:50:24

2.4K00

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

1. 问题引入

前面讲了0-1背包的回溯解决方法，它是穷举所有可能，复杂度是指数级别的，如何降低时间复杂度呢？

对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？

假设背包的最大承载重量是9。有5个不同的物品，重量分别是2，2，4，6，3。把回溯求解过程，用递归树画出来，就是下面这个样子：

从上面图中可以看出有些函数被重复计算（之前递归中也讲到了），我们希望当计算到已经计算过的函数时，不要重复计算，直接拿来用，避免重复劳动。

还是前面的0-1背包问题，分别添加和不添加重复计算判断语句，查看效果

#include <iostream>
#define MaxWeight 9   //背包承载极限
using namespace std;
bool mem [5][9];
int counttimes;
void fill(int i, int curWeight, int *bag, int N, int &maxweightinbag)
{
    cout << "调用次数: " << ++counttimes << endl;
    if(curWeight == MaxWeight || i == N)//到达极限了，或者考察完所有物品了
    {
        if(curWeight > maxweightinbag)
            maxweightinbag = curWeight;//记录历史最大装载量
        return;
    }
    //-----注释掉以下3行查看效果-------
    if(mem[i][curWeight])
        return;
    mem[i][curWeight] = true;
    //---------------------------------
    fill(i+1,curWeight,bag,N,maxweightinbag);//不选择当前i物品，cw不更新
    if(curWeight+bag[i] <= MaxWeight)//选择当前i物品，cw更新
    {//没有达到极限，继续装
        fill(i+1,curWeight+bag[i],bag,N,maxweightinbag);
    }
}
int main()
{
    const int N = 5;
    int bag[N] = {2,2,4,6,3};
    int maxweightinbag = 0;
    fill(0,0,bag,N,maxweightinbag);
    cout << "最大可装进背包的重量是：" << maxweightinbag;
    return 0;
}

2. 动态规划求解0-1背包

把整个求解过程分为n个阶段，每个阶段会决策一个物品是否放到背包中。每个物品决策（放入或者不放入背包）完之后，背包中的物品的重量会有多种情况，也就是说，背包会达到多种不同的状态，对应到递归树中，就是有很多不同的节点。
把每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。我们可以通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过MaxWeight个（MaxWeight表示背包的承载极限）。于是，我们就成功避免了每层状态个数的指数级增长。
用一个二维数组states[N][MaxWeight+1], 来记录每层可以达到的不同状态

bag[N] = {2,2,4,6,3}; MaxWeight = 9

第0个（下标从0开始编号）物品的重量是2，要么装，要么不装，决策完之后，会对应背包的两种状态，背包中物品的总重量是0或者2。我们用states[0][0]=true和states[0][2]=true 来表示这两种状态。

第1个物品的重量也是2，基于之前的背包状态，在这个物品决策完之后，不同的状态有3个，背包中物品总重量分别是0（0+0），2（0+2 or 2+0），4（2+2）。我们用states[1][0]=true，states[1][2]=true，states[1][4]=true来表示这三种状态。

只需要在最后一层，找一个值为true的最接近 MaxWeight（这里是9）的值，就是背包中物品总重量的最大值。

/**
 * @description: 0-1背包--dp应用
 * @author: michael ming
 * @date: 2019/7/9 1:13
 * @modified by: 
 */
#include <iostream>
#define MaxWeight 9   //背包承载极限
const int N = 5;    //背包个数
using namespace std;
bool states[N][MaxWeight+1];//全局参数自动初始化，默认是false
int fill_dp(int *bag, int N)
{
    states[0][0] = true;//第1个背包不放
    if(bag[0] <= MaxWeight)
        states[0][bag[0]] = true;//第1个背包放
    for(int i = 1; i < N; ++i)//动态规划状态转移
    {
        for(int j = 0; j <= MaxWeight; ++j)//不把第i个物品放入背包
        {
            if(states[i-1][j] == true)
                states[i][j] = states[i-1][j];//把上一行的状态复制下来（i不放物品）
        }
        for(int j = 0; j+bag[i] <= MaxWeight; ++j)
            if(states[i-1][j] == true)
                states[i][j+bag[i]] = true;//把第i个物品放入背包
    }
    for(int i = MaxWeight; i >= 0; --i)//把最后一行，从后往前找最重的背包
    {
        if(states[N-1][i] == true)
            return i;//最大重量
    }
    return 0;
}
int main()
{
    int bag[N] = {2,2,4,6,3};
    cout << "最大可装进背包的重量是：" << fill_dp(bag,N);
    return 0;
}

3. 复杂度

上面就是一种用动态规划解决问题的思路。把问题分解为多个阶段，每个阶段对应一个决策。记录每一个阶段可达的状态集合（去掉重复的），然后通过当前的状态集合，来推导下一阶段的状态集合，动态地往前推进。

用回溯算法解决这个问题的时间复杂度O（2n），是指数级的。
上面DP代码耗时最多的部分是代码中的两层for循环，所以时间复杂度是O（N * MaxWeight）。N表示物品个数，MaxWeight表示背包承载极限。
尽管动态规划的执行效率比较高，但是就上面DP代码实现来说，我们需要额外申请一个N*（MaxWeight+1）的二维数组，对空间的消耗比较多。所以，动态规划是一种空间换时间的解决思路。有什么办法可以降低空间消耗吗？
实际上，我们只需要一个大小为 MaxWeight+1 的一维数组就可以解决这个问题。动态规划状态转移的过程，都可以基于这个一维数组来操作。具体的代码如下。

/**
 * @description: 
 * @author: michael ming
 * @date: 2019/7/15 22:00
 * @modified by: 
 */
#include <iostream>
#define MaxWeight 9   //背包承载极限
const int N = 5;    //背包个数
using namespace std;
bool states[MaxWeight+1];//全局参数自动初始化，默认是false
int fill_dp(int *bag, int N)
{
    states[0] = true;//第1个背包不放
    if(bag[0] <= MaxWeight)
        states[bag[0]] = true;//第1个背包放
    for(int i = 1; i < N; ++i)//动态规划状态转移
    {
        for(int j = MaxWeight-bag[i]; j >= 0; --j)//把第i个物品放入背包
        {
            if(states[j] == true)
                states[j+bag[i]] = true;
        }
    }
    for(int i = MaxWeight; i >= 0; --i)//输出结果
    {
        if(states[i] == true)
            return i;//最大重量
    }
    return 0;
}
int main()
{
    int bag[N] = {2,2,4,6,3};
    cout << "最大可装进背包的重量是：" << fill_dp(bag,N);
    return 0;
}

内层for循环，j 需要从大到小处理，如果从小到大，会出现重复计算

4. 0-1背包升级版（带价值）

每个物品对应着一种价值，不超过背包载重极限，求可装入背包的最大总价值。

//--------回溯解法-------------------
int maxV = -1; // 最大价值放到 maxV 中
int weight[5] = {2,2,4,6,3};  // 物品的重量
int value[5] = {3,4,8,9,6}; // 物品的价值
int N = 5; // 物品个数
int MaxWeight = 9; // 背包承受的最大重量
void f(int i, int cw, int cv) 
{ // 调用 f(0, 0, 0)
	if (cw == MaxWeight || i == N) 
	{ // cw==MaxWeight 表示装满了，i==N 表示物品都考察完了
    	if (cv > maxV) 
    		maxV = cv;
    	return;
	}
  	f(i+1, cw, cv); // 选择不装第 i 个物品
  	if (cw + weight[i] <= w) 
  	{
    	f(i+1, cw+weight[i], cv+value[i]); // 选择装第 i 个物品
  	}
}

对上面代码画出递归树，每个节点表示一个状态。现在我们需要3个变量（i，cw，cv）来表示一个状态。其中，i表示即将要决策第i个物品是否装入背包，cw表示当前背包中物品的总重量，cv表示当前背包中物品的总价值。

我们发现，在递归树有几个节点的 i 和 cw 是完全相同的，比如（2，2，4）和（2，2，3）。
在背包中物品总重量一样的情况下，f（2，2，4）这种状态的物品总价值更大，可以舍弃 f（2，2，3）这种状态，只需要沿着 f（2，2，4）这条决策路线继续往下决策就可以。
也就是，对于（i，cw）相同的不同状态，只需要保留 cv 值最大的那个，继续递归处理，其他状态不予考虑。

5. 0-1背包升级版（带价值）DP解法

把整个求解过程分为n个阶段，每个阶段会决策一个物品是否放到背包中。
每个阶段决策完之后，背包中的物品的总重量以及总价值，会有多种情况。
用一个二维数组 states[N][MaxWeight+1]，来记录每层可以达到的不同状态。
这里数组存储的值不再是bool类型的了，而是当前状态对应的最大总价值。
把每一层中（i，cw）重复的状态（节点）合并，只记录cv值最大的那个状态，然后基于这些状态来推导下一层的状态。

/**
 * @description: 0-1背包带价值，dp解法
 * @author: michael ming
 * @date: 2019/7/16 0:07
 * @modified by: 
 */
#include <iostream>
#define MaxWeight 9   //背包承载极限
const int N = 5;    //背包个数
using namespace std;
int fill_value_dp(int* weight, int* value, int N)
{
    int (*states) [MaxWeight+1]  = new int [N][MaxWeight+1];
    for (int i = 0; i < N; ++i) // 初始化 states
    {
        for (int j = 0; j < MaxWeight+1; ++j)
            states[i][j] = -1;
    }
    states[0][0] = 0;//第一个不放，价值0存入states
    if (weight[0] <= MaxWeight)
    {
        states[0][weight[0]] = value[0];//第一个放入背包
    }
    for (int i = 1; i < N; ++i) // 动态规划，状态转移
    {
        for (int j = 0; j <= MaxWeight; ++j)
        { // 不选择第 i 个物品
            if (states[i-1][j] >= 0)
                states[i][j] = states[i-1][j];//直接复制上一层的状态
        }
        for (int j = 0; j+weight[i] <= MaxWeight; ++j)
        { // 选择第 i 个物品
            if (states[i-1][j] >= 0)
            {
                int v = states[i-1][j] + value[i];
                if (v > states[i][j+weight[i]])
                {//只存价值最大的
                    states[i][j+weight[i]] = v;
                }
            }
        }
    }
    // 找出最大值
    int maxvalue = -1;// 最大价值放到 maxvalue 中
    for (int j = 0; j <= MaxWeight; ++j)
    {
        if (states[N-1][j] > maxvalue)
            maxvalue = states[N-1][j];
    }
    delete [] states;
    return maxvalue;
}
int main()
{
    int weight[5] = {2,2,4,6,3};  // 物品的重量
    int value[5] = {3,4,8,9,6}; // 物品的价值
    cout << "最大可装进背包的价值是：" << fill_value_dp(weight,value,N);
    return 0;
}

时间和空间复杂度都是O(N * MaxWeight)

使用一维数组也可DP解题，空间复杂度减小为O（MaxWeight）

/**
 * @description: 0-1背包带价值，dp解法(状态存储用一维数组)
 * @author: michael ming
 * @date: 2019/7/16 22:17
 * @modified by: 
 */
#include <iostream>
#define MaxWeight 9   //背包承载极限
const int N = 5;    //背包个数
using namespace std;
int fill_value_dp(int* weight, int* value, int N)
{
    int *states  = new int [MaxWeight+1];
    for (int i = 0; i < MaxWeight+1; ++i) // 初始化 states
    {
        states[i] = -1;
    }
    states[0] = 0;//第一个不放，价值0存入states
    if (weight[0] <= MaxWeight)
    {
        states[weight[0]] = value[0];//第一个放入背包
    }
    for (int i = 1; i < N; ++i) // 动态规划，状态转移
    {
        for (int j = MaxWeight-weight[i]; j >= 0; --j)
//        for (int j = 0; j <= MaxWeight-weight[i]; ++j)
        { // 选择第 i 个物品
            if (states[j] >= 0)
            {
                int v = states[j] + value[i];
                if (v > states[j+weight[i]])
                {//只存价值最大的
                    states[j+weight[i]] = v;
                }
            }
        }
    }
    // 找出最大值
    int maxvalue = -1;// 最大价值放到 maxvalue 中
    for (int i = 0; i <= MaxWeight; ++i)
    {
        if (states[i] > maxvalue)
            maxvalue = states[i];
    }
    delete [] states;
    return maxvalue;
}
int main()
{
    int weight[N] = {2,2,4,6,3};  // 物品的重量
    int value[N] = {3,4,8,9,6}; // 物品的价值
    cout << "最大可装进背包的价值是：" << fill_value_dp(weight,value,N);
    return 0;
}

最大可装进背包的价值是：18 一维数组变化过程如下：

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/07/16 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度