【算法设计与分析】动态规划 - 背包问题详解（基础背包）

一时失言乱红尘 2022-11-21 14:49 175阅读 0赞

### 文章目录 ###

*  前言
 *  0-1背包
 *   *  问题描述
     *  问题解析
     *  性能优化：状态压缩
 *  完全背包
 *   *  基本思路
     *  细节上的优化
 *  多重背包
 *   *  基本思路
     *  效率优化
 *  总结
 *  参考资料

# 前言 #

最近又把背包系列问题温习了一遍，打算写篇文章将常见的几类背包问题进行总结，提取背包问题核心套路，在自己理解的同时，用通俗的语言解释，让看完本文的人能够快速上手解决一系列的背包问题。

--------------------

内容包含如下：

*  **从基础开始：0-1背包问题**
 *  **再进一步：完全背包**
 *  **顺手拈来：多重背包**
 *  **变形：其他背包问题**

> 限于篇幅问题，拟将该系列拆成两篇，第一篇包含上面三个部分，实际上是对三种基础类型有一定掌握，第二篇，主要讲解基于三种类型衍生而来的背包问题和实际（面试）经常遇到的。

# 0-1背包 #

要讲背包问题，都得从0-1背包这个最基础问题开始，基本上能够熟练掌握0-1背包，对付其他的背包问题也问题不大。

## 问题描述 ##

![在这里插入图片描述][20201102101626106.png_pic_center]

有 N N N件物品和一个容量为 W W W的背包，第 i i i件物品消耗的容量为 w i w\_i wi，价值为 W i W\_i Wi，求解放入哪些物品可以使得背包中总价值最大。

--------------------

上述问题还可以用一个形象的例子描述，就是：

> 一个小偷，进入主人家偷东西，能偷的东西非常多（如电视机，金表，洋娃娃），但是你的包裹容量有限，如何才能不虚此行？

## 问题解析 ##

问题了解了，产生问题的根本原因在于能力有限（容量），性价比不一（物品）。其实很容易想到暴力的解法，每个物品都有**放和不放**两种选择，那么把所有可能的选择列出来，选择价值最大的就可以了。

但是这样计算成本很高 O ( 2 n ) O(2^n) O(2n)，因此采用动态规划的方式。

动态规划的方法实际上也是考虑了**放与不放**两种情况，但它与暴力不同的一点是，他会利用到之前的结果，而不是将每个物品独立来看。

--------------------

*  明确**状态**与**选择**

这里需要引入动态规划中的两个概念：**状态**和**选择**，所有动态规划问题都绕不开这两个核心，**状态**表示了动态规划中会变化的内容，**选择**则是我们每一步的岔路口，不同的选择会引发不同的状态。

在背包问题中，我们将整个过程从1-N循序渐进，可以发现过程中会变化的东西有两个：**背包的容量**（放入后减小），**可选择的物品**（选择过后从选择列表去除），这就是**状态**。而**选择**就很容易了，我们只有**放与不放**两种选择，每一次选择都会引发状态的变化（容量减小或可选择物品减少）。

*  **定义dp数组**

当明确这两点后，再看我们的需求：**给定容量下的最大价值**。它主要受限于**状态**：

*  如果可选择的物品更多（性价比更高），那么最大价值会更高
 *  如果背包容量更大，那么最大价值会更高

因此，我们可以定义一个动态数组 d p \[ i \] \[ w \] dp\[i\]\[w\] dp\[i\]\[w\]，它表示，在前 i i i个可选择物品中，容量为 w w w时，能得到的最大价值。根据这个定义，我们可以知道，最终要求的就是 d p \[ n \] \[ W \] dp\[n\]\[W\] dp\[n\]\[W\]

> 解答一下为什么这么定义: 动态规划问题能够加速计算的核心在于有一个动态数组存储了计算结果，避免了不必要的重复计算，我们在定义这个数组的时候，要向我们的目标靠拢，同时需要考虑所有状态的限制。

--------------------

*  **确定状态转移**

前面我们依据**状态**定义了dp数组，接下来要根据**选择**去更新dp数组。选择无非**放与不放**（针对第i个物品），将这一点结合到dp数组上体现就是：

*  **不放**：即不将第i个物品放入背包，那么 d p \[ i \] \[ w \] dp\[i\]\[w\] dp\[i\]\[w\]就和 d p \[ i − 1 \] \[ w \] dp\[i-1\]\[w\] dp\[i−1\]\[w\]一样，相当于没有变化
 *  **放**：当放入物品时，总容量减少第i个物品的容量，总价值提升第i个物品的价值，有 d p \[ i \] \[ w \] = d p \[ i − 1 \] \[ w − w i − 1 \] + v i − 1 dp\[i\]\[w\]=dp\[i-1\]\[w-w\_\{i-1\}\] + v\_\{i-1\} dp\[i\]\[w\]=dp\[i−1\]\[w−wi−1\]\+vi−1
    
    > 这里 w i − 1 , v i − 1 w\_\{i-1\},v\_\{i-1\} wi−1,vi−1是因为程序中默认0是第一个，所以 i − 1 i-1 i−1就是第i个

接着考虑一下边缘情况(base case)：

*  当容量为0时，总价值为0： d p \[ . . . \] \[ 0 \] = 0 dp\[...\]\[0\] = 0 dp\[...\]\[0\]=0
 *  当可选择物品为0时，总价值为0： d p \[ 0 \] \[ . . . \] = 0 dp\[0\]\[...\] = 0 dp\[0\]\[...\]=0

综上，我们已经可以得到解决该问题的伪代码：

dp[0][...] = 0
    dp[...][0] = 0
    for i in [1,N]:  # 所有可选择物品
    	for w in [1, W]:  # 总容量
    		dp[i][w] = max(dp[i-1][w], dp[i-1][w-w[i-1]]+v[i-1])  # 比较放与不放取最大价值

到此，基本上算理解0-1背包的思想了，但距离实际解决0-1背包还差一点内容：

*  编写实际代码，考虑下标出界情况
 *  编写一个小例子，观察过程中dp数组的变化

第一个编写实际代码能够更好地巩固0-1背包的思想，毕竟理论去说和实际去写还是有一定的差别。下面是我写的c++代码

int knapsack(int W, int N, vector<int>& wt, vector<int>& val) { 
        // 初始化一个二维数组， dp[i][w] 表示对前i个物品，当容量为w时能够装的最大价值
        vector<vector<int>> dp(N+1, vector<int>(W+1,0));  // dp[N+1][W+1] 0
        for(int i=1;i<=N;i++){ 
            for(int w=1;w<=W;w++){ 
                if(w-wt[i-1]<0){ 
                    // 装不下
                    dp[i][w] = dp[i-1][w];
                }else{ 
                    dp[i][w] = max(dp[i-1][w-wt[i-1]]+val[i-1], dp[i-1][w]);
                }
            }
        }
        
        return dp[N][W];
    }

第二个编写一个小例子是我个人的建议，当了解了dp数组的动态变化过程后，会有一个更直观的感受。下面是我撰写的例子，假设背包容量4，3个物品，对应的 w i , v i w\_i,v\_i wi,vi分别是 \[ 2 , 3 , 1 \] , \[ 4 , 5 , 2 \] \[2,3,1\],\[4,5,2\] \[2,3,1\],\[4,5,2\]  
![在这里插入图片描述][20201102120634202.png_pic_center]

> 箭头表示状态转移过程

## 性能优化：状态压缩 ##

在作图的过程中，可以发现第i列一定是从第i-1列转移过来的（要么是左上角，要么是左边），每一次i的变化，都是在更新一列的数据，因此我们实际上不需要保存整个二维数组，只需要保存一列的数据，并在循环中不断更新呢它就好了。

--------------------

因此，重新定义 d p \[ w \] dp\[w\] dp\[w\]表示容量为w时，能够获取的最大价值，当循环更新完毕后，保存的 d p \[ w \] dp\[w\] dp\[w\]就是容量为w，物品为n时的最大价值（即最后一列数据）

这里直接给出代码：

int knapsack(int W, int N, vector<int>& wt, vector<int>& val) { 
        vector<int> dp(W+1,0); 
        for(int i=1;i<=N;i++){ 
            for(int w=W;w>=wt[i-1];w--){ 
            	dp[w] = max(dp[w-wt[i-1]]+val[i-1], dp[w]);
            }
        }
        return dp[W];
    }

这里面有一个特殊的点，就是w的更新方向改成了逆序，这个是必要的，因为我们知道每次状态转移，都会用到左边或左上角的数据，如果w采用正序，那么会使得依赖的i-1的数据被更新，导致计算错误，如下：  
![在这里插入图片描述][2020110214160475.png_pic_center]  
而如果逆序更新的话，结果如下：  
![在这里插入图片描述][20201102142012759.png_pic_center]

# 完全背包 #

完全背包是0-1背包的一次变体，将原来问题中每个物品只有一个的属性改成了无数个，这使得对某一物品的选择可以是多次。

## 基本思路 ##

实际上虽然说是无限，但由于背包容量有限，每个物品的最大个数还是不超过 W w \[ i − 1 \] \\frac\{W\}\{w\[i-1\]\} w\[i−1\]W个。那么我们可以直接通过将单个 w \[ i − 1 \] w\[i-1\] w\[i−1\]的无限物品转换为 W w \[ i − 1 \] \\frac\{W\}\{w\[i-1\]\} w\[i−1\]W个相同的有限物品，就可以将完全背包转换为0-1背包问题。

我们先从最简单的思路入手，同样是转移，只不过多了一层循环，我们可以选择一次放多个，很容易得到伪代码如下：

dp[0][...] = 0
    dp[...][0] = 0
    for i in [1,N]:  # 所有可选择物品
    	for w in [1, W]:  # 总容量
    		for k in [0, w/wt[i-1]]:
    		dp[i][w] = max(dp[i][w], dp[i-1][w-k*wt[i-1]]+k*v[i-1])  # 比较放与不放取最大价值

相比于之前的0-1背包，主要变化的有两点：

*  多了一层k循环，用于指定选择物品的个数
 *  更新的时候，依次比较放0个第i个物品，放一个第i个物品，…，那种放法得到的价值最大

但这三重循环使得时间复杂度骤增，主要是对单个物品的计算成本提高了。这里就结合上面的转换0-1背包的思想，将单个 w \[ i − 1 \] w\[i-1\] w\[i−1\]的无限物品转换为 W w \[ i − 1 \] \\frac\{W\}\{w\[i-1\]\} w\[i−1\]W个相同的有限物品，但仅仅这样并没有减小时间复杂度。

--------------------

在这里，我们回顾一下之前0-1背包做状态压缩的过程，之所以采用逆序，是因为后面的状态依赖前面的，当前面状态先被更新，会导致后面状态不准确。换句话说，如果前面状态先被更新（表示物品i被选择了一次），后面状态如果在此基础上继续更新（还要不要选物品i），就体现出了物品i被选择了多次，这刚好符合完全背包的思想。没理解不急，看下面的例子：  
![在这里插入图片描述][20201102145029740.png_pic_center]  
第二次选择基于第一次物品3已经被选择的基础上，又选择了一次物品3，相当于物品3被选择两次。注意原本0-1背包中**绿色状态**的改变依赖于左边**蓝色**列的数据，而当正序遍历的时候，由于蓝色的值被覆盖，导致了绿色依赖于被覆盖后的数据，这样，一轮循环中，如果该物品可以被选择，同时选择后的结果比之前高，那么就更新状态。

> 这部分的理解可能较难，建议对着图中的数据，自己一笔一笔推敲思考。

由上我们得到新的完全背包伪代码：

for i in [1,N]:  # 所有可选择物品
    	for w in [1, W]:  # 总容量
    		dp[w] = max(dp[w-wt[i-1]]+val[i-1], dp[w]);

> 本质上就是将w的遍历次序颠倒一下

## 细节上的优化 ##

在实际应用中，对于同样体积的物品而言，我们还可以只保留价值最高的物品，将其他的物品过滤掉，比如A，B容量都为5，但是A价值10，B价值5，那么B可以直接不用考虑了。

# 多重背包 #

多重背包将完全背包中物品数量的限制从无限改成了给定的数量，例如物品A,B,C，每个数量分别为5，4，7，价值分别为6，5，7，重量分别是6，4，9，背包容量依旧为W，求最大价值。

## 基本思路 ##

我们可以借鉴完全背包一开始的模板：

dp[0][...] = 0
    dp[...][0] = 0
    for i in [1,N]:  # 所有可选择物品
    	for w in [1, W]:  # 总容量
    		for k in [0, n[i]]:
    		dp[i][w] = max(dp[i][w], dp[i-1][w-k*wt[i-1]]+k*v[i-1])

上面只是将物品的可选择数`k`的范围修改限定到了指定的范围当中。这种方法易于理解，同时实现简便，缺点就是复杂度高。

--------------------

## 效率优化 ##

其实有了完全背包的经验，我们可以很轻易将多重背包问题转换成0-1背包问题解决，只要将同类型的每个物品单独看作一个物品即可。但如果每次都是单独一个物品进行叠加计算，本质上和上面的方法复杂度没什么两样。下面采取一种二进制表示的思想进行优化：

回顾背包问题，无非就涉及到**状态**和**选择**两个变量。我们将同一类物品按照数量划分成n个相同的物品，比较每个物品选择与否，取最大值，只要我们实现每一种选择表示都能被取到，那么都能达到选择的目的，例如某一类物品有10个，我们需要比较从0-10，11个选择中 d p \[ i \] \[ w \] dp\[i\]\[w\] dp\[i\]\[w\]最大的结果，如果是将10个分成10堆，每次一个一个添加，是可以遍历所有的情况，但结合二进制的思想我们知道，我们不必每次都是选择一个，可以一次选择4个，2个，8个等，重点在于0-10这11个选择情况都能被遍历到。

像上面的10个物品，我们可以将其划分成1，2，4，3，这样4堆，他们的组合可以得到0-10中任意一个选择。比如7=4+2+1，8=4+3+1。这样的话可以大大节省过程中比较的时间。

> 这部分的思想可能比较难以消化，需要理解动态规划本质上还是要考虑所有物品取与放的情况，一个比较形象的例子是设想到超市抢购苹果，一个一个拿和一次拿一大堆，再拿一小堆，两者的效率显而易见了。

因此，上述方法用代码实现只要将每次选择的k从1，2，3，转变成1，2，4即可。伪代码具体如下：

for(i=1; i<=N;i++)   # N种物品
    	num = min(n[i], W/w[i])   # 不超过总容量下可选取的最多物品个数
    	for(k=1; num > 0; k <<=1)  # k每次乘2
    		if(k>num) k = num
    		num -= k    # k=1,2,4,3
    		for(j=W; j>=w[i]*k; j--)
    			dp[j] = max(dp[j], dp[j-w[i]*k]+k*v[i])  # 取k个和不取

# 总结 #

本文讲述了0-1，完全，多重三种基础类型的背包，其核心在于**状态**和**选择**，只要搞懂这两样，解决背包问题自然顺手拈来。同时，还有一些优化的思想（包括状态压缩、二进制表示），背包问题选择的本质，都是值得反复琢磨、思考的，希望本文能给你学习背包问题带来一点启发。

# 参考资料 #

*  https://github.com/tianyicui/pack
 *  https://blog.csdn.net/yandaoqiusheng/article/details/84782655

[20201102101626106.png_pic_center]: /images/20221120/27326341b814429eba04de6fb61ed8b9.png
[20201102120634202.png_pic_center]: /images/20221120/d6b4330707f143fab6115b77ba744387.png
[2020110214160475.png_pic_center]: /images/20221120/626003d9d582472bb98ad4b1be41720f.png
[20201102142012759.png_pic_center]: /images/20221120/70301ade2a954579ac3e6b073842510f.png
[20201102145029740.png_pic_center]: /images/20221120/0f52baf003114005844886fa5b5b73c4.png