背包型 | Civilization Museum

type

status

password

date

slug

summary

0-1背包问题

题目描述

有件物品和一个容量为的背包。放入第件物品耗费的容量是，得到的价值是。求解将哪些物品装入背包可使价值总和最大。每种物品仅有一件，可以选择放或不放

输入：背包的容量，每件物品耗费的容量，以及价值是。

输出：背包的最大价值

题解

如果当前背包里面物品总价值是，背包当前容量是。对于每一个物品可以考虑放，或者不放，面对第个物品，如果取这个物品，背包总价值会变成，背包容量会变成。

状态：dp[i][C] 表示前件物品，放入一个容量为的背包可以获得的最大价值。

边界条件：我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。

如果要求恰好装满背包，那么在初始化时除了 dp[i][0] 为 0，其它 dp[i][C] 均设为，这样就可以保证最终得到的 dp[i][C] 是一种恰好装满背包的最优解。因为，如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为了。对于第 0 件商品，如果背包的容量等于C[0]恰好装满，则 dp[0][C]=v[0] if C==c[0]。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 dp[i][C] 全部设为 0。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。对于第 0 件商品，如果背包的容量大于c[0]，则 dp[0][C]=v[0] if C>=c[0]。

状态转移方程：给定了背包容量的情况下，前类物品恰放入背包的最大总价值这个子问题只需要考虑第 个物品是否放入背包。当前物品不放入背包的情况下，当前总价值与前个物品恰放入容量的背包的总价值相等；而如果放入背包，则留给前个物品的背包容量将会减小，当前总价值与前个物品恰放入容量的背包的总价值加上当前物品价值相等。所以状态转移方程如下所示：

空间优化

dp 数组当前行的计算只用到了前一行，我们可以利用 滚动数组 来优化，但是再仔细看下去的话，你就会发现其实还可以更优，当前行的遍历用到的值是上一行的前面列的值，如果我们第二层 for 循环遍历的时候倒着遍历的话，保证了前面更新的值不会被新计算的值覆盖掉，我们仅仅用一维数组就可以完美解决问题。

统一代码

面对装满以及恰好装满两种文法，可以统一代码。初始化、初始条件都与恰好装满相同，初始化全部设为负无穷，唯一区别在于返回最终结果。在最终返回结果时，如果是恰好装满背包，则返回；如果不要求恰好装满背包，则返回中的最大值。

空间优化

完全背包

题目描述

有件物品和一个容量为的背包。放入第件物品耗费的容量是，得到的价值是。求解将哪些物品装入背包可使价值总和最大。每个物品有无限个可用。

输入：背包的容量，每件物品耗费的容量，以及价值是。

输出：背包的最大价值

优化

完全背包问题有两个很简单有效的优化，是这样的：

若两件物品满足且，则将可以将物品直接去掉，不用考虑。

若物品耗费的容量，可以将物品直接去掉。

题解一

完全背包问题看上去只和0-1背包问题有很小的区别，区别在于完全背包问题每种物品可选的数目是任意的。我们从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取 0 件、取 1 件、取 2 件……直至取 件(背包容量是 ，第 种背包耗费的容量是,那么最多取 件)。这样我们就可以将完全背包问题转化为0-1背包问题。将每类物品，变为件物品。

把第种物品拆成费用为、价值为的若干件物品，其中取遍满足的非负整数。这是二进制的思想。因为不管最优策略选几件第种物品，其件数写成二进制后，总可以表示成若干个件物品的和。这样一来就把每种物品拆成件物品，是一个很大的改进。

题解二

完全背包问题看上去只和0-1背包问题有很小的区别，区别在于完全背包问题每种物品可选的数目是任意的。我们从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取 0 件、取 1 件、取 2 件……直至取 件(背包容量是 ，第 种背包耗费的容量是,那么最多取 件)。可以推导出完全背包的动态规划转移公式：

状态：dp[i][C] 表示前类物品，放入一个容量为的背包可以获得的最大价值。

边界条件：我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。

如果要求恰好装满背包，那么在初始化时除了 dp[i][0] 为 0，其它 dp[i][C] 均设为，这样就可以保证最终得到的 dp[i][C] 是一种恰好装满背包的最优解。因为，如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为了。对于第 0 类商品，如果背包的容量为c[0]的整倍数，恰好装满，则 dp[0][C]=k*v[0] k = C//c[0]。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 dp[i][C] 全部设为 0。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。对于第 0 件商品，如果背包的容量大于c[0]，则 dp[0][C]=k*v[0] k =C//c[0]。

状态转移方程：给定了背包容量的情况下，前类物品恰放入背包的最大总价值这个子问题只需要考虑第 类物品有几件放入背包。当有件商品放入背包时，则留给前类物品的背包容量将会减小，当前总价值与前个物品恰放入容量的背包的总价值加上当前物品价值相等。所以状态转移方程如下所示：

空间优化

统一代码

空间优化

多重背包

题目描述

有件物品和一个容量为的背包。放入第件物品耗费的容量是，得到的价值是，共有件。求解将哪些物品装入背包可使价值总和最大。

输入：背包的容量，每件物品耗费的容量、价值、数量。

输出：背包的最大价值

优化

完全背包问题有两个很简单有效的优化，是这样的：

若两件物品满足且，则将可以将物品直接去掉，不用考虑。

若物品耗费的容量，可以将物品直接去掉。

题解一

多重背包问题，转化为 0-1 背包求解：把第种物品换成件 0-1 背包中的物品，则得到了物品数为的 0-1 背包问题。

。把第种物品拆成费用为、价值为的若干件物品，其中取遍满足的非负整数。这是二进制的思想。因为不管最优策略选几件第种物品，其件数写成二进制后，总可以表示成若干个件物品的和。这样一来就把每种物品拆成件物品，是一个很大的改进。

题解二

多重背包问题和完全背包问题很类似，区别在于多重背包问题每种物品可选的数目是有限制的。我们只需要对完全背包问题加上限制条件，我们就可以将多重背包问题转化为完全背包问题。我们基于完全背包问题，可以推导出它的动态规划转移公式为：

状态：dp[i][C] 表示前类物品，放入一个容量为的背包可以获得的最大价值。

边界条件：我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。

如果要求恰好装满背包，那么在初始化时除了 dp[i][0] 为 0，其它 dp[i][v] 均设为，这样就可以保证最终得到的 dp[i][v] 是一种恰好装满背包的最优解。因为，如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为了。对于第 0 类商品，如果背包的容量为c[0]的整倍数，恰好装满，则 dp[0][v]=k*w[0] k = v//c[0] & k <= m[0]。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 dp[i][C] 全部设为 0。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。对于第 0 件商品，如果背包的容量大于c[0]，则 dp[0][C]=k*v[0] k =C//c[0] & k <= m[0]。

状态转移方程：给定了背包容量的情况下，前类物品恰放入背包的最大总价值这个子问题只需要考虑第 类物品有几件放入背包。当有件商品放入背包时，则留给前类物品的背包容量将会减小，当前总价值与前个物品恰放入容量的背包的总价值加上当前物品价值相等。所以状态转移方程如下所示：

空间优化

统一代码

空间优化

混合3种背包问题

题目描述

如果将前面1、2、3中的三种背包问题混合起来。也就是说，有的物品只可以取一次（01 背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。

二维费用的背包问题

题目描述

有件物品和一个容量为、承重为的背包。放入第件物品耗费的容量是，重量是，得到的价值是。求解将哪些物品装入背包可使价值总和最大。每种物品只有一件。

题解一

二维费用背包问题的费用加了一维，只需状态也加一维即可。设 dp[i,C,W] 表示前件物品付出两种费用分别为和时可获得的最大价值。我们基于0-1背包问题，可以推导出它的动态规划转移公式为：

状态：dp[i][C][W] 表示前类物品，放入一个容量为、承重为的背包可以获得的最大价值。

边界条件：我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。

如果要求恰好装满背包，那么在初始化时除了 dp[i][0][0] 为 0，其它 dp[i][C][W] 均设为，这样就可以保证最终得到的 dp[i][C][W] 是一种恰好装满背包的最优解。因为，如果要求背包恰好装满，那么此时只有容量为 0 且承重为 0的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为了。对于第 0 件商品，如果背包的容量等于C[0]恰好装满，则 dp[0][C][W]=v[0] if C==c[0] W=w[0]。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 dp[i][C][w] 全部设为 0。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。对于第 0 件商品，如果背包的容量大于c[0]容量，承重大于w[0]，则 dp[0][C][W]=v[0] if C>=c[0] W>=w[0]。

状态转移方程：给定了背包容量、承重为的情况下，前类物品恰放入背包的最大总价值这个子问题只需要考虑第 个物品是否放入背包。当前物品不放入背包的情况下，当前总价值与前个物品恰放入容量、承重为的背包的总价值相等；而如果放入背包，则留给前个物品的背包容量将会减小，当前总价值与前个物品恰放入容量、承重为的背包的总价值加上当前物品价值相等。所以状态转移方程如下所示：

空间优化

如前述优化空间复杂度的方法，可以只使用二维的数组：当每件物品只可以取一次时变量和采用逆序的循环，当物品有如完全背包问题时采用顺序的循环，当物品有如多重背包问题时拆分物品。

统一代码

空间优化

分组的背包问题

题目描述

有件物品和一个容量为的背包。放入第件物品耗费的容量是，得到的价值是。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使价值总和最大。

统一代码

题解一

这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设 dp[k][C]表示前组物品花费费用能取得的最大权值。状态转移方程就是：

状态：dp[k][C] 表示前组物品，放入一个容量为的背包可以获得的最大价值。

边界条件：我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。

如果要求恰好装满背包，那么在初始化时除了 dp[k][0] 为 0，其它 dp[i][C] 均设为，这样就可以保证最终得到的 dp[k][C] 是一种恰好装满背包的最优解。因为，如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为了。对于第 0 件商品，如果背包的容量等于C[0]恰好装满，则。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 dp[i][C] 全部设为 0。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。对于第 0 组商品，如果背包的容量大于c[i]，则 dp[0][j]= max(v[i]) if j>=c[i]。

状态转移方程：给定了背包容量的情况下，前类物品恰放入背包的最大总价值这个子问题只需要考虑是选择第 组的某一件，还是一件都不选。如果本组一件商品都不放入背包的情况下，当前总价值与前组物品恰放入容量的背包的总价值相等；而如果第组的第件放入背包，则留给前组物品的背包容量将会减小，当前总价值与前组物品恰放入容量的背包的总价值加上当前物品价值相等。所以状态转移方程如下所示：

空间优化

统一代码

空间优化

泛化物品

题目描述

考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。这个定义有一点点抽象，另一种理解是一个泛化物品就是一个数组 h[0..V]，给它费用v，可得到价值h[V]。

背包问题问法的变化

以上涉及的各种背包问题都是要求在背包容量（费用）的限制下求可以取到的最大价值，但背包问题还有很多种灵活的问法，例如，求解最多可以放多少件物品或者最多可以装满多少背包的空间。这都可以根据具体问题利用前面的方程求出所有状态的值（dp 数组）之后得到。

计算最小价值

如果要求的是“总价值最小”、“总件数最小”，只需将状态转移方程中的 max 改成 min 即可。

输出方案

一般而言，背包问题是要求一个最优值，如果要求输出这个最优值的方案，可以参照一般动态规划问题输出方案的方法：记录下每个状态的最优值是由状态转移方程的哪一项推出来的。

💡

用一个数组，设表示推出的值时是未选第个物品（也即）；表示采用了方程的后一项，选了第个物品（也即）。

输出字典序最小的最优方案

字典序：例如4321这字符串它可以有4321 3214 2143 1234当然这一眼就能够看出 1234 是最小的；43215 1234 两个字符串中字典序最小的是 1234。

💡

字典序的比较原则首先比较第1个字符，如果不同则第1个字符较小的字符串更小，一直这样子比较下去。

题解

题目要求输出字典序最小的解，假设存在一个包含第1个物品的最优解，为了确保字典序最小那么我们必然要选第一个。那么问题就转化成从这些物品中找到最优解。之前的记录的都是前个物品总容量为的最优解，那么我们现在将定义为从第个元素到最后一个元素总容量为的最优解。接下来考虑状态转移：

下面我们以是否选取第一个元素为例，介绍方案的转移过程：

如果，说明选取了第1个物品可以得到最优解。

如果，说明不选取第一个物品才能得到最优解。

如果，说明选不选都可以得到最优解，但是为了考虑字典序最小，我们也需要选取该物品。

求方案总数

求装满背包或将背包装至某一指定容量的方案总数。对于这类改变问法的问题，一般只需将状态转移方程中的 max 改成 sum 即可。例如若每件物品均是完全背包中的物品，转移方程即为

初始条件是。

最优方案的总数

这里的最优方案是指物品总价值最大的方案。以 01 背包为例。最优方案的总数可以这样求：代表该状态的最大价值，表示这个子问题的最优方案的总数:

求次优解、第 K 优解

设表示前件物品，放入容量为的背包中，可以获得的最大价值。表示第件物品的体积，表示第件物品的价值，则有:

现在我们要求前个最优解,则在滚动数组的基础上增加一维，设表示体积为时的第优解的值。显然, 是一个单调递减的序列.

💡

注意，如统一代码中一样

当求k优解时。不管问题要求恰好装满背包，还是不装满背包时，问题的初始化是一样的。只是在最终返回结果时，如果是恰好装满背包，则返回 ；如果不要求恰好装满背包，则返回dp中第k大的值。对于0-1背包同时也可以使用这种方法，初始化为负无穷，在最终返回结果时，如果是恰好装满背包，则返回 ；如果不要求恰好装满背包，则返回dp中的最大值。

空间优化

使用滚动数组，优化空间复杂度，则有:

我们发现只可能由或者推来，且一定等于两者中的较大者。现在我们要求前个最优解,则在滚动数组的基础上增加一维，设表示体积为时的第优解的值。显然, 是一个单调递减的序列.

注意，当求k优解时。不管问题要求恰好装满背包还是，不装满背包时，问题的初始化是一样的。只是在最终返回结果时，如果是恰好装满背包，则返回 ；如果不要求恰好装满背包，则返回dp中第k大的值。对于0-1背包同时也可以使用这种方法，初始化为负无穷，在最终返回结果时，如果是恰好装满背包，则返回 ；如果不要求恰好装满背包，则返回dp中的最大值。