首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >小朋友学经典算法(16):动态规划之背包问题

小朋友学经典算法(16):动态规划之背包问题

作者头像
海天一树
发布2019-03-14 14:35:43
5130
发布2019-03-14 14:35:43
举报
文章被收录于专栏:海天一树海天一树

背包问题泛指以下这一种问题: 给定一组有固定价值和固定重量的物品,以及一个已知最大承重量的背包,求在不超过背包最大承重量的前提下,能放进背包里面的物品的最大总价值。 这一类问题是典型的使用动态规划解决的问题,我们可以把背包问题分成3种不同的子问题:0-1背包问题、完全背包和多重背包问题。下面对这三种问题分别进行讨论。

一、0-1背包

0-1背包问题是指每一种物品都只有一件,可以选择放或者不放。现在假设有n件物品,背包承重为m。 对于这种问题,我们可以采用一个二维数组去解决:f[i][j],其中i代表加入背包的是前i件物品,j表示背包的承重,f[i][j]表示当前状态下能放进背包里面的物品的最大总价值。那么,f[n][m]就是我们的最终结果了。 采用动态规划,必须要知道初始状态和状态转移方程。初始状态很容易就能知道,那么状态转移方程如何求呢?对于一件物品,我们有放进或者不放进背包两种选择: (1)假如我们放进背包,f[i][j] = f[i - 1][j - weight[i]] + value[i],这里的f[i - 1][j - weight[i]] + value[i]应该这么理解:在没放这件物品之前的状态值加上要放进去这件物品的价值。而对于f[i - 1][j - weight[i]]这部分,i - 1很容易理解,关键是 j - weight[i]这里,我们要明白:要把这件物品放进背包,就得在背包里面预留这一部分空间。 (2)假如我们不放进背包,f[i][j] = f[i - 1][j],这个很容易理解。 因此,我们的状态转移方程就是:f[i][j] = max(f[i][j] = f[i - 1][j] , f[i - 1][j - weight[i]] + value[i]) 当然,还有一种特殊的情况,就是背包放不下当前这一件物品,这种情况下f[i][j] = f[i - 1][j]。这种场景可以用来初如化f[i][j]。

下面是实现的代码:

#include <iostream>
#include <iostream>
using namespace std;

#define V 500
#define N 20
int weight[N + 1];
int value[N + 1];
int f[N + 1][V + 1];

int main()
{
    int n, m;
    cout << "请输入物品个数:";
    cin >> n;

    cout << "请分别输入" << n << "个物品的重量和价值:" << endl;
    for (int i = 1; i <= n; i++)
    {
        cin >> weight[i] >> value[i];
    }

    cout << "请输入背包容量:";
    cin >> m;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (weight[i] > j)
            {
                f[i][j] = f[i - 1][j];  // 初始化,假定背包放不下当前这一件物品
            }
            else
            {
                f[i][j] = max(f[i - 1][j], f[i - 1][j - weight[i]] + value[i]);
            }
        }
    }

    cout << "背包能放的最大价值为:" << f[n][m] << endl;

    return 0;
}

应用例子:采药 山洞里有三株不同的草药,采第一株需要71分钟,采第二株需要69分钟,采第三株需要1分钟。第一株的价值为100,第二株的价值为1,第三侏的价值为2。给你70分钟的时间,你可以让采到的草药的最大的总价值是多少?

分析: 这就是一个0-1背包问题,总时间70分钟相当于背包的承重能力,采每株草药的时间相当于每个物品的重量。 直接运行上面的程序,可得到结果:

请输入物品个数:3
请分别输入3个物品的重量和价值:
71 100
69 1
1 2
请输入背包容量:70
背包能放的最大价值为:3

代码分析:

用i表示当前采了几种草药,j表示用了多少时间

(1)采第一种草药i = 1,所需时间weight[1] = 71,价值value[1] = 100 j = 1时,f[1][1] = f[0][1] = 0 j = 2时,f[1][2] = f[0][2] = 0 j = 3时,f[1][3] = f[0][3] = 0 …… j = 70时,f[1][70] = f[0][70] = 0

(2)前两种草药i = 2,weight[2] = 69,value[2] = 1 j = 1时,f[2][1] = f[1][1] = 0 j = 2时,f[2][2] = f[1][2] = 0 j = 3时,f[2][3] = f[1][3] = 0 …… j = 68时,f[2][68] = f[1][68] = 0 j = 69时,j >= weight[i], f[2][69] = max(f[1][69], f[1][0] + value[2]) = max(0, 0 + 1) = 1。max函数中的第一个参数f[1][69]表示采第一株草药用掉全部69单位的时间能获取到的价值,因为第一株草药需要100单位的时间,所以f[1][69]得到的价值为0;第二个参数f[1][0] + value[2]表示采第一株草药用了0单位时间,价值为0,把剩余的69的时间全用在采第二株草药上,得到的价值为1。 j = 70时,j >= weight[i], f[2][70] = max(f[1][70], f[1][1] + value[2] = max(0, 0 + 1) = 1。max函数中的第一个参数f[1][70]表示采第一株草药用掉全部70单位的时间能获取到的价值,因为第一株草药需要100单位的时间,所以f[1][70]得到的价值为0;第二个参数f[1][1] + value[2]表示采第一株草药用了1单位时间,因为采第一草药需要100单位的时间,所以1单位时间不够采第一株草药,得到的价值为0,把剩余的69的时间全用在采第二株草药上,得到的价值为1。

(3)前三种草药i = 3,weight[3] = 1,value[3] = 2 j = 1时,j >= weight[i], f[3][1] = max(f[2][1], f[2][0] + value[3]) = max(0, 0 + 2) = 2,max中的第一个参数表示把这1秒的时间用来采前两株草药,第二个参数表示用前0秒的时间采前两株草药,用剩余1秒的时间采第三株草药。 j = 2时,j >= weight[i], f[3][2] = max(f[2][2], f[2][1] + value[3]) = max(0, 0 + 2) = 2 j = 3时,j >= weight[i], f[3][3] = max(f[2][3], f[2][2] + value[3]) = max(0, 0 + 2) = 2 …… j = 68时,j >= weight[i], f[3][68] = max(f[2][68], f[2][67] + value[3]) = max(0, 0 + 2) = 2 j = 69时,j >= weight[i], f[3][69] = max(f[2][69], f[2][68] + value[3]) = max(1, 0 + 2) = 2。max函数的第一个参数f[2][69]表示把69单位的时间用在采前两株草药,事实上只能采到第二株草药,价值为1。第二个参数中的f[2][68]表示前68单位的时间用来采前两株草药,无法采到草药,价值为0;value[3]表示把最后一秒的时间用来采第三株草药,得到的价值为2。 j = 70时,f[3][70] = f[2][70] = 0,此时j >= weight[i], f[3][70] = max(f[2][70], f[2][69] + value[3]) = max(1, 1 + 2) = 2 =3。max函数的第一个参数f[2][70]表示把70单位的时间用在采前两株草药,事实上只能采到第二株草药,价值为1。第二个参数中的f[2][69]表示前69单位的时间用来采前两株草药,可以采到第二株草药,价值为1;value[3]表示把最后一秒的时间用来采第三株草药,得到的价值为2,二者加起来即总价值为3。

0-1背包问题还有一种更加节省空间的方法,那就是采用一维数组去解决,下面是代码:

#include <iostream>
#include <algorithm>
using namespace std;

#define V 500
int weight[20 + 1];
int value[20 + 1];
int f[V + 1];
int main()
{
    int n, m;
    cout << "请输入物品个数:";
    cin >> n;

    cout << "请分别输入" << n << "个物品的重量和价值:" << endl;
    for (int i = 1; i <= n; i++)
    {
        cin >> weight[i] >> value[i];
    }

    cout << "请输入背包容量:";
    cin >> m;

    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= 1; j--)
        {
            if (weight[i] <= j)
            {
                f[j] = max(f[j], f[j - weight[i]] + value[i]);
            }
        }
    }

    cout << "背包能放的最大价值为:" << f[m] << endl;

    return 0;
}

代码分析: 1 仍以采草药的例子为例,总时间m = 70,草药数量n = 3。 (1)i = 1, weight[1] = 71 j = 70, weight[1] <= j为假。 j = 69, weight[1] <= j为假。 …… j = 2, weight[1] <= j为假。 j = 1, weight[1] <= j为假。

(2)i = 2, weight[2] = 69 j = 70, weight[2] <= j为真,f[70] = max(f[70], f[1] + value[2]) = max(0, 0 + 1) = 1。max函数中的第一个参数f[70]表示70分钟的时间用来采第一株草药。第二个参数f[1] + value[2]表示把前1分钟的时间用来采第一株草药,把剩下的69分钟时间用来采第二株草药。 j = 69, weight[2] <= j为真,f[60] = max(f[69], f[0] + value[2]) = max(0, 0 + 1) = 1。f[0] + value[2]表示把前0分钟的时间用来采第一株草药,把剩下的69分钟用来采第二株草药。 j = 68, weight[2] <= j为假。 …… j = 1, weight[2] <= j为假。

(3)i = 3, weight[3] = 1 j = 70, weight[3] <= j为真,f[70] = max(f[70], f[69] + value[3]) = max(1, 1 + 2) = 3。max函数中的第一个参数f[70],根据i=2中的f[70]可知是表示前1分钟的时间用来采第一株草药后69分钟的时间用来采第二株草药。第二个参数f[69] + value[3]表示前69分钟的时间用来采前两株草药(具体是前0分钟的时间采第一株后69分钟的时间采第二株),最后一秒用来采第三株。 j = 69, weight[3] <= j为真,f[69] = max(f[69], f[68] + value[3]) = max(1, 0 + 2) = 2。max函数中的第一个参数f[69]表示这69分钟的时间用来采前两株草药的最大价值,根据i=2中的f[69]可知具体是前0分钟的时间用来采第一株草药后69分钟的时间用来采第二株草药。第二个参数f[68] + value[3]表示前68分钟的时间用来采前两株草药,最后一秒用来采第三株。 …… j = 2, weight[3] <= j为真,f[2] = max(f[2], f[1] + value[3]) = max(0, 0 + 2) = 2。max函数中的第一个参数f[2]表示前个分钟的时间用来采前两株草药。第二个参数f[1] + value[3]表示前1分钟的时间用来采前两株草药,最后一秒用来采第三株。 j = 1, weight[3] <= j为真,f[1] = max(f[1], f[0] + value[3]) = max(0, 0 + 2) = 2。max函数中的第一个参数f[1]表示这一秒的时间用来采前两株草药。第二个参数f[0] + value[3]表示前0分钟的时间用来采前两株草药,最后一秒用来采第三株。

(4)最后,f[m] = f[70]即是所求的答案。

2 第二个for循环里面,j为什么要从大到小枚举,而不是从小到大枚举? 假如j是从小到大枚举,则代码为:

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        if (weight[i] <= j)
        {
            f[j] = max(f[j], f[j - weight[i]] + value[i]);
        }
    }
}

i = 2,j = 69时,f[69] = max(f[69], f[0] + value[2]) = max(0, 0 + 1) = 1。 i = 2,j = 70时,f[70] = max(f[70], f[1] + value[2]) = max(0, 0 + 1) = 1。 i = 3,j = 1时,f[1] = max(f[1], f[0] + value[3]) = max(0, 0 + 2) = 2。max函数中的第一个参数f[1]表示这1分钟的时间用来采前两株草药,f[0] + value[3]表示前0分钟的时间用来采前两株草药,剩余1分钟的时间用来采第三株草药。 i = 3,j = 2时,f[2] = max(f[2], f[1] + value[3]) = max(0, 2 + 2) = 4。ax函数中的第一个参数f[1]表示这2分钟的时间用来采前两株草药,f[1] + value[3]中的f[1]根据i = 3, j = 1的情景表示前0分钟的时间用来采前两株草药,第1分钟的时间用来采第三株草药,value[3]表示第2秒的时间用来采第三株草药。注意这里第三株草药在第1分钟的时间里采了一次,第2分钟又采了一次,所以出错。

可以把下一段代码

for (int i = 1; i <= n; i++)
{
    for (int j = m; j >= 1; j--)
    {
        if (weight[i] <= j)
        {
            f[j] = max(f[j], f[j - weight[i]] + value[i]);
        }
    }
}

进一步简化为:

for (int i = 1; i <= n; i++) 
{
    for (int j = m; j >= weight[i]; j--) 
    {
         f[j] = max(f[j], f[j - weight[i]] + value[i]);
    }
}

二、完全背包

完全背包和01背包十分相像, 区别就是完全背包中的每种物品有无限件。由之前的选或者不选转变成了选或者不选、选的话要选几件。下面给出实现代码:

#include <iostream>
#include <algorithm>

using namespace std;

#define V 500
int weight[20 + 1];
int value[20 + 1];
int f[V + 1];

int main()
{
    int n, m;
    cout << "请输入物品个数:";
    cin >> n;

    cout << "请分别输入" << n << "个物品的重量和价值:" << endl;
    for (int i = 1; i <= n; i++)
    {
        cin >> weight[i] >> value[i];
    }

    cout << "请输入背包容量:";
    cin >> m;

    for (int i = 1; i <= n; i++)
    {
        for (int j = weight[i]; j <= m; j++)
        {
            f[j] = max(f[j], f[j - weight[i]] + value[i]);
        }
    }

    cout << "背包能放的最大价值为:" << f[m] << endl;

    return 0;
}

仍以上面的采草药为例,运行结果为:

请输入物品个数:3
请分别输入3个物品的重量和价值:
71 100
69 1
1 2
请输入背包容量:70
背包能放的最大价值为:140

分析: 1 完全背包的代码与0-1背包的代码只有一行区别。完全背包中的j是从小到大按顺序枚举的,而0-1背包中的j是从大到小逆序枚举的。

2 程序执行过程 (1)i = 1时,j = weight[i] = 71, j <= m为假,循环不执行。

(2)i = 2时,weight[2] = 69,value[2] = 1 j = 69, f[69] = max(f[69], f[0] + value[2]) = max(0, 0 + 1) = 1。max中的第一个参数f[69]表示把69分钟的时间用于第一株草药,价值是0。第二个参数中的f[0]表示前0分钟采到到草药的总价值,value[2]表示剩下的69分钟用于采第2株草药。 j = 70, f[70] = max(f[70], f[1] + value[2]) = max(0, 0 + 1) = 1。max中的第一个参数f[70]表示把70分钟的时间用于第一株草药,价值是0。第二个参数中的f[1]表示前1分钟采到到草药的总价值,value[2]表示剩下的69分钟用于采第2株草药。

(3)i = 3时,weight[3] = 1, value[3] = 2 j = 1, f[1] = max(f[1], f[0] + value[3]) = max(0, 0 + 2) = 2。max中的第一个参数f[1]表示把1分钟的时间用于采前两株草药,价值是0。第二个参数中的f[0]表示前0分钟采到草药的总价值,value[3]表示剩下的1分钟用于采第3株草药。 j = 2, f[2] = max(f[2], f[1] + value[3]) = max(0, 2 + 2) = 4。max中的第一个参数f[2]表示把2分钟的时间用于采前两株草药,价值是0。第二个参数中的f[1]表示前1分钟采到草药的总价值,value[3]表示剩下的1分钟用于采第3株草药。 j = 3, f[3] = max(f[3], f[2] + value[3]) = max(0, 4 + 2) = 6。max中的第一个参数f[3]表示把3分钟的时间用于采前两株草药,价值是0。第二个参数中的f[2]表示前2分钟采到草药的总价值,value[3]表示剩下的1分钟用于采第3株草药。 …… j = 68, f[68] = max(f[68], f[67] + value[3]) = max(0, 134 + 2) = 136。max中的第一个参数f[68]表示把68分钟的时间用于采前两株草药,价值是0。第二个参数中的f[67]表示前67分钟采到到草药的总价值,value[3]表示剩下的1分钟用于采第3株草药。 j = 69, f[69] = max(f[69], f[68] + value[3]) = max(1, 136 + 2) = 138。max中的第一个参数f[69]表示把69分钟的时间用于采前两株草药,价值是1。第二个参数中的f[68]表示前68分钟采到到草药的总价值,value[3]表示剩下的1分钟用于采第3株草药。 j = 70, f[70] = max(f[70], f[69] + value[3]) = max(1, 138 + 2) = 140。max中的第一个参数f[70]表示把70分钟的时间用于采前两株草药,价值是1。第二个参数中的f[69]表示前69分钟采到草药的总价值,value[3]表示剩下的1分钟用于采第3株草药。

三、多重背包

多重背包问题限定了一种物品的个数,解决多重背包问题,只需要把它转化为0-1背包问题即可。比如,有2件价值为5,重量为2的同一物品,我们就可以分为物品a和物品b,a和b的价值都为5,重量都为2,但我们把它们视作不同的物品。 实现代码:

#include <iostream>
#include <algorithm>
using namespace std;

#define V 1000
int weight[50 + 1];
int value[50 + 1];
int num[20 + 1];
int f[V + 1];

int main()
{
    int n, m;
    cout << "请输入物品个数:";
    cin >> n;

    cout << "请分别输入" << n << "个物品的重量、价值和数量:" << endl;
    for (int i = 1; i <= n; i++)
    {
        cin >> weight[i] >> value[i] >> num[i];
    }

    int k = n + 1;
    for (int i = 1; i <= n; i++)
    {
        while (num[i] != 1)
        {
            weight[k] = weight[i];
            value[k] = value[i];
            k++;
            num[i]--;
        }
    }
    k--;

    cout << "请输入背包容量:";
    cin >> m;

    for (int i = 1; i <= k; i++)
    {
        for (int j = m; j >= weight[i]; j--)
        {
            f[j] = max(f[j], f[j - weight[i]] + value[i]);
        }
    }

    cout << "背包能放的最大价值为:" << f[m] << endl;

    return 0;
}

仍旧以采草药为例,运行结果:

请输入物品个数:3
请分别输入3个物品的重量、价值和数量:
71 100 2
69 1 2
1 2 2
请输入背包容量:70
背包能放的最大价值为:4

分析: (1)第二个for的作用是将同样的物品进行拆分。 weight[4] = weight[1]; value[4] = value[1]; weight[5] = weight[2]; value[5] = value[2]; weight[6] = weight[3]; value[6] = value[3];

(2)最终拆分后的物品总数量k = 6。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-02-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 信息学竞赛NOIP 微信公众号,前往查看

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

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、0-1背包
  • 二、完全背包
  • 三、多重背包
相关产品与服务
腾讯云代码分析
腾讯云代码分析(内部代号CodeDog)是集众多代码分析工具的云原生、分布式、高性能的代码综合分析跟踪管理平台,其主要功能是持续跟踪分析代码,观测项目代码质量,支撑团队传承代码文化。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档