小朋友学经典算法（16）：动态规划之背包问题

约定不等于承诺〃 2022-03-17 07:38 211阅读 0赞

背包问题泛指以下这一种问题：  
给定一组有固定价值和固定重量的物品，以及一个已知最大承重量的背包，求在不超过背包最大承重量的前提下，能放进背包里面的物品的最大总价值。  
这一类问题是典型的使用动态规划解决的问题，我们可以把背包问题分成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。

> 少儿编程咨询、算法咨询请加微信307591841或QQ群581357582  
> ![信息学竞赛公众号.jpg][.jpg]

[.jpg]: /images/20220317/8f429f34142349ac84e325cc9d840103.png