背包问题 | Serendipity

type

status

date

slug

summary

简介

背包问题（英语：Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中，背包的空间有限，但我们需要最大化背包内所装物品的价值。背包问题通常出现在资源分配中，决策者必须分别从一组不可分割的项目或任务中进行选择，而这些项目又有时间或预算的限制。

背包问题历史悠久，甚至可以追溯到1897年。“背包问题” 一词最早出现于数学家托比阿斯·丹齐格的早期研究中，他研究的问题是如何打包行李，要求最大化所选行李的价值且不能超载。

背包问题出现在现实世界很多领域的决策过程中，诸如寻找节约原料的生产方式、选择投资项目及投资组合、选择证券化的资产以及为默克尔-赫尔曼和其他背包密码系统生成密钥。

背包问题中基础的大致分为一下几类：

0-1背包

解释

例题中已知条件有第个物品的重量，价值，以及背包的总容量。

设 DP 状态为在只能放前个物品的情况下，容量为的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前个物品的所有状态，那么对于第 i 个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为；当其放入背包时，背包的剩余容量会减小，背包中物品的总价值会增大，故这种情况的最大价值为。由此可以得出状态转移方程：

这里如果直接采用二维数组对状态进行记录，会出现 MLE。可以考虑改用滚动数组的形式来优化。（将二维数组优化写成一维数组）

由于对有影响的只有，可以去掉第一维，直接用来表示处理到当前物品时背包容量为的最大价值，得出以下方程:

核心代码：

需要注意的是，第二个循环的枚举的顺序是从枚举到。为什么呢？

如果从枚举到在时，是会被所影响的，如果前面放入物品是价值更大，我们会将其放入并更新，在后面时如果再次选择放入会用到这就相当于物品可以多次被放入背包，与题意不符。（事实上，这正是完全背包问题的解法）。

如果二维 DP 不会爆 MLE 我们也可以用二维 DP 来处理，此时第二个循环的枚举顺序不影响结果，因为对于任意的并不会修改或者的结果。代码如下：

完全背包

解释

完全背包模型与 0-1背包类似，与 0-1背包的区别仅在于一个物品可以选取无限次.。

我们可以借鉴 0-1背包的思路，进行状态定义：设为只能选前个物品时，容量为的背包可以达到的最大价值。

可以考虑一个朴素的做法：对于第件物品，枚举其选了多少个来转移。这样做的时间复杂度是的。状态转移方程如下：

考虑做一个简单的优化。可以发现，对于，只要通过转移就可以了。当我们这样转移时，已经由更新过，那么就是充分考虑了第i件物品所选次数后得到的最优结果。换言之，我们通过局部最优子结构的性质重复使用了之前的枚举过程，优化了枚举的复杂度。因此状态转移方程为:

与 0-1背包相同，我们可以将第一维去掉来优化空间复杂度。

核心代码：

多重背包

解释

多重背包是 0-1背包的一个变式。与 0-1背包的区别在于每种物品有个，而非一个。

一个很朴素的想法就是：我们把个相同的物品看成个重量价值相同但是不同的物品，即对个物品做 0-1背包。

时间复杂度。

核心代码：

二进制分组优化

显然，复杂度中的部分无法再优化了，我们只能从处入手。

为了表述方便，我们用代表第种物品拆分出的第个物品。

在朴素的做法中，，均表示相同物品。那么我们效率低的原因主要在于我们进行了大量的重复性的工作。举例来说，我们考虑了同时选，与同时选，这两个完全等效的情况。这样的重复性工作我们进行了许多次。那么优化拆分方式就成为了解决问题的突破口。

我们可以通过二进制分组的方式使拆分方式更加优美。具体地说就是令分别表示由个单个物品捆绑而成的大物品。特殊地，若不是的整数次幂，则需要在最后添加一个由个单个物品捆绑而成的大物品用于补足。

例如：

8=1+2+4+1

18=1+2+4+8+3

31=1+2+4+8+16

显然，通过上述拆分方式，可以表示任意个物品的等效选择方式。将每种物品按照上述方式拆分后，使用 0-1背包的方法解决即可。

时间复杂度。

分组背包

解释

有件物品和一个大小为的背包，第个物品的价值为，体积为。同时，每个物品只属于一个组，同组内最多只能选择一个物品，求背包能装载物品的最大总价值。

其实是从在所有物品中选择一件变成了从当前组中选择一件，于是就对每一组进行一次 0-1 背包就可以了，再说一说如何进行存储。我们可以将t表示第k组的第i件物品的编号是多少，再用表示第组物品有多少个。

核心代码：

混合背包

解释

混合背包是 0-1背包、完全背包以及多重背包的组合，会出现其中的几种背包。有些可以无限取，有些物品只可以取有限次。

把不同情况分开：

能无限选 → 按完全背包处理。

选择次数有限 → 按多重（0-1）背包处理。

分情况分别解决，最后合并即可。

前言 · 背包问题九讲 · 看云 (kancloud.cn)