背包问题总结 - 徒手拆机甲 - 博客园

说到动态规划，背包问题是大家都绕不开的一个问题，这篇文章将从最简单的01背包问题开始，尽可能详细的给大家介绍各种背包问题的解法

首先，背包问题中最简单的问题也就是这个01背包问题，我们先一起来看一下这个问题

我们需要判断的是，对于每一个物品，是选择他更好，还是不选择他更好。不管是贪心还是枚举都不能很好的解决这个问题，这时候我们需要用动态规划的方式解决这个问题，

首先我们要设计出问题的状态f [i] [j]定义：前 i个物品，背包容量 j下的最优解（最大价值）：

当前的状态依赖于之前的状态，可以理解为从初始状态f[0] [0] = 0开始决策，有 N 件物品，则需要 N 次决 策，每一次对第 i 件物品的决策，状态f[i] [j]不断由之前的状态更新而来。

1.当前背包容量不够（j < v[i]），没得选，因此前 i 个物品最优解即为前 i−1 个物品最优解这时候我们直接转移状态f[i] [j] = f[i - 1] [j]。

2.当前背包容量够，可以选，因此需要决策选与不选第 i 个物品：也就是要找的这两种情况的最优解。

选：f[i] [j] = f[i - 1] [j - v[i]] + w[i]。

不选：f[i] [j] = f[i - 1] [j] 。

我们的决策是如何取到最大价值，因此以上两种情况取 max() 。

为什么这个问题的结果可以成立，因为我们的每个状态都记录的是当前局部状态下的最优解，而每次更新新的物品时，我们一定是从之前的原始转态转移过来的，所以说不会影响后续结果的变化。话不多说，大家可以通过下面的代码来理解这个问题。

代码做的其实很简单，就是对于每个物品，都把所有体积枚举一遍，保证所有情况都会被考虑到，不重不漏。接下来给大家介绍一个关于优化01背包问题空间复杂度的方法。

其实原理很简单，就是每次的f[I] [J]的值都是从i-1转移过来的，所以我们可以定义f时直接忽略第一维，然后倒序枚举所有用到的体积

二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i] [j]与f[i - 1] [j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。如果采用倒序的方法，我们每次更新的j都是用上一维的j直接进行转移的，由于枚举体积是倒序进行，不会导致用到被覆盖过的结果，可以节省一些空间复杂度

具体写法就是

说完了01背包，接下来给大家介绍的是完全背包问题，因为大部分背包问题基本原理都大致相同，所以之后所有问题，都会讲他变化的地方，

先来看一下完全背包和01背包的区别

其实区别就是，每个物品的数量不做限制了，我们先和刚刚一样，用最朴素的写法尝试理解这个问题

实际上，我们只是对于每个体积多了一次枚举选择几个该物品的过程，实际上，我们也可以吧问题理解成，选一个第i个物品是一个状态，选2个是一个状态，...这样问题就转化成了01背包问题。理解了之后，我们考虑如何优化这个问题。

对于这个问题，其实我们理解f [i] [j]=max(f[i,j-v]+w , f[i-1] [ j]) 也就是说，在体积从小到大枚举的过程中，我们可以记录已经选了一个该物品的结果，来考虑需不需要考虑是否选择第二个物品。不需要第三层循环来限制选择的数量每个体积都会被上次该体积的结果直接更新,也就是下面这样。

和刚刚的01背包基本一样，唯一的区别就是这里max里的第二项下标从i-1变成了i。也就是说，我们直接在这一维的基础上继续考虑是否继续选择这个物品，在优化一下空间

最朴素的想法就是，把问题拆成01背包问题来解决

简单点写的话

不过，这种方法能解决问题的范围是相当有限的，如果想要解决更大规模的问题，我们需要进一步优化

我们令 dp[j] 表示容量为j的情况下，获得的最大价值

那么，针对每一类物品 i ，我们都更新一下 dp[m] --> dp[0] 的值，最后 dp[m] 就是一个全局最优值

显而易见，m 一定等于 k * v + j，其中 0 <= j < v

所以，我们可以把 dp 数组分成 j 个类，每一类中的值，都是在同类之间转换得到的

也就是说，dp[k * v+j] 只依赖于 { dp[j], dp[v+j], dp[2v+j], dp[3v+j], ... , dp[kv+j] }

因为我们需要的是{ dp[j], dp[v+j], dp[2v+j], dp[3*v+j], ... , dp[k * v+j] } 中的最大值，

可以通过维护一个单调队列来得到结果。这样的话，问题就变成了 j 个单调队列的问题、

层层递进，维护v次单调队列，每次都更新每个体积下的最优解，最后剩下的记过就是最优解。

问题和01背包基本一致，只是需要多加一维判断体积维度的。倒着一起枚举就行。

分组背包要求，每组物品只有一个物品可以最后被使用，为了达到这个目的，我们就像01背包一样，每一种都选择一遍，实际上也可以理解成多重背包，就是选1个是一种方案，选2个也是一种方案，最后都看做01背包来解决这个问题。

在讲有依赖的背包问题之前，我们前介绍一个这类题目的前身，也是2006年NOIP提高组的一个题目

题意就是，给你一些物品组合，必须买了主件才能购买附件，实际上，这不是严格的有依赖背包问题，但有依赖背包问题是在这个问题之后被提出的。所以我们先来看一下这个问题，实际上，观察后可以发现，这道题其实就是一种分组背包，举个例子，如果有1个主件，2个附件对于每一个主件，我们看成一组，这组物品中，有全都不选，只选主件，选主件和附件1，选主件和附件2，全都选5种情况共同组成。我们只需要按照分组背包的方式来枚举所有情况即可，为了方便统计所有情况，我们可以用二进制枚举的技巧，很简单就能枚举出所有情况。有一些细节可以再代码找到对应的体现。

其实大体思路还是按照分组背包来选择，需要结合树形dp来一起完成。对于每个子树，根节点是一定要选的，对于子树中的内容，我们就按照分组背包来枚举所有的选法组合，找到可获得体积的最大值。区别是子树的节点可能会过多，会导致搜索深度过大，我们只能按照体积划分所有子树的可能选择方式。给每个子树分配0到总体积减根体积的体积，来看给定体积后，可以选到的最大值。

最后，背包问题的变化还有很多，本文也不可能全部覆盖，希望他可以帮助你对背包问题有一点新的理解，如果浪费了你的时间，那就先说声抱歉，也希望你能早日理解背包问题，如果有什么地方错误，欢迎评论或私信指出，谢谢大家