背包问题九讲学习小记[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

有些大佬小学就啃完背包问题九讲了，%%%%%。 细节落实要细致。

1 01背包 2完全背包 3多重背包 4 123讲的综合 5二维费用的背包问题 6分组背包 7依赖性背包 8泛化物品 9一些变式

先呈上2张概念图表。

解释此图。 背包问题是DP问题中的一种。问题的模型是，将一些物品（有序地/无序地）放入有容量的背包，然后问最大价值，或者其他问题。 物品的概念：一般的物品，有固定的体积、价值；泛化物品，就是物品的容量和价值是不固定的，换句话说，物品的价值随它的容量而变化。泛化物品能够表示所有的物品。 背包有如下几种： 基础的：01背包，多重背包，完全背包。实际上将多重背包，完全背包的物品进行拆分后，都是01背包。 综合的： 分组背包。每组物品只能够选其中的0件或1件。 01,多重,完全背包的混合（解决问题的方法：只需判断该物品属于哪种背包即可）。 二维费用背包。就是背包的体积是二维的，对应地，还可以理解为花费是二维的。 依赖性背包：就是树形背包。 变式：学会了这一部分的问题能够解决其他的一些DP问题。

通过解决背包问题，我学会了解决某些DP的技巧。 空间上，时间上，还有搜索顺序上的。 时间的优化是最主要的，通过 O ( V ) O(V) O(V)的时间去重，让每种容量的物品只保留最高价值的。 通过 O ( K ) O(K) O(K)的时间选取最优值，也是一种巧妙的技巧。我记得，NOIP2016蚯蚓的那题的解题思路的基本原理跟这个相差无几。

这两张图表中的知识似乎没有联系？ 看下面的图。

按照箭头的颜色以及编号，先谈对这些优化的理解。 优化1，如果01背包的空间减小一维，那么枚举容量的时候需倒序。 优化2，通过合并物品，在DP中枚举物品的件数，转化为01背包问题。（描述得有点不清楚） 优化3，单调队列优化，通过改变枚举背包容量的方式，将 O ( V ∗ ∑ m [ i ] ) O(V*sum m[i]) O(V∗∑m[i])的复杂度将至 O ( V N ) O(VN) O(VN) 优化4，将 m m m个物品的限制，可以拆成 l o g log log个物品，从而表达出 0… m [ i ] 0…m[i] 0...m[i]这些物品的数量。 优化5，从小到大枚举容量。 优化6，见优化2。 优化7，见优化2。 优化8，见优化5。 优化9，见优化4。 优化10，选择附件的方式能够将一些有冲突的物品归为一组。广泛地，选出一些有冲突的物品，归为一组。做分组背包问题。 优化11，通过 O ( K ) O(K) O(K)的时间选取最优值，也是一种巧妙的技巧。 优化12，改变枚举物品的方式，比如按照编号从大到小枚举。 优化原理：DP状态及他们之间的转移关系可视为DAG，寻找最优方案的时候，记录的是目前的最优值通过走DAG中的哪条边得来。这能够应用于寻找字典序最小最优解。 优化13，基于DFS序的背包解决树形依赖背包。记住，在DP的时候，枚举DFS序究竟是顺序的，还是倒序的，这个要很清楚。 优化14，让相同容量的物品，只保留价值最大的那一个。这可以应用到所有的背包问题中。 然而这也只是DP的解决方案中的冰山一角，下面就是要学的内容。

前3讲分别讲得是01背包，完全背包以及多重背包。 后面6讲讲得是综合性的问题。 看完这9讲之后，尝试对各种背包问题归类。 最重要地，背包问题要与其他DP问题联系起来。

一般地，设背包容量为 C C C，设每个物品的体积为 v [ i ] v[i] v[i]，每个物品的价值为 w [ i ] w[i] w[i] 对于01背包： 每种物品最多只有1件。

时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( n ) O(n) O(n)

对于完全背包（无限背包） 每个物品有无限件。 实际上每件物品最多只有 ⌊ C v [ i ] ⌋ lfloorfrac{C}{v[i]} floor ⌊v[i]C​⌋件。 没有优化的： f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i − 1 ] [ j − k ∗ v [ i ] ] + k ∗ w [ i ] ) f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]) f[i][j]=max(f[i][j],f[i−1][j−k∗v[i]]+k∗w[i]) 优化①，如果 w [ i ] ≤ w [ j ] , v [ i ] ≥ v [ j ] w[i]≤w[j],v[i]≥v[j] w[i]≤w[j],v[i]≥v[j]，显然将物品 j j j删除。 但这个优化没优化多少。 优化②，将 ⌊ C v [ i ] ⌋ lfloorfrac{C}{v[i]} floor ⌊v[i]C​⌋转化为二进制。 比如 ⌊ C v [ i ] ⌋ = 13 lfloorfrac{C}{v[i]} floor=13 ⌊v[i]C​⌋=13，拆成 1 , 4 , 8 1,4,8 1,4,8 则问题转化为01背包。 这个优化使效率提高了不少。 优化③ 将代码改为：

为什么对？ 因为j正着循环，考虑了物品i放 [ 1 , ⌊ C v [ i ] ⌋ ] [1,lfloorfrac{C}{v[i]} floor] [1,⌊v[i]C​⌋]个的情况。

多重背包：第i种物品最多有 m [ i ] m[i] m[i]件。 问题的转化：转化为01背包和完全背包问题。 比如 m [ i ] = 13 m[i]=13 m[i]=13，拆成 1 , 4 , 8 1,4,8 1,4,8 如果 m [ i ] ≥ ⌊ C v [ i ] ⌋ m[i]geqlfloorfrac{C}{v[i]} floor m[i]≥⌊v[i]C​⌋，则第i种物品归属完全背包。 否则归属01背包。 时间复杂度： O ( C ∗ ∑ m [ i ] ) O(C*sum m[i]) O(C∗∑m[i]) 当然，更优的做法： 希望用单调队列来解决此问题。 优化原理：取模的思想。 f [ j ] = m a x ( f [ j − k ∗ v [ i ] ] + k ∗ w [ i ] ) f[j]=max(f[j-k*v[i]]+k*w[i]) f[j]=max(f[j−k∗v[i]]+k∗w[i]) j可以看成 k ∗ v [ i ] + b k*v[i]+b k∗v[i]+b 考虑另外一种枚举的方式。 枚举b（余数） 现在要求 ( f [ k ∗ v [ i ] + b ] − k ∗ w [ i ] ) (f[k*v[i]+b]-k*w[i]) (f[k∗v[i]+b]−k∗w[i])的最大值。 首先， f [ k ∗ v [ i ] + b ] = m a x ( f [ ( a − k ) v [ i ] + b ] + k ∗ w [ i ] ) f[k*v[i]+b]=max(f[(a-k)v[i]+b]+k*w[i]) f[k∗v[i]+b]=max(f[(a−k)v[i]+b]+k∗w[i]) 令 k ′ = a − k k'=a-k k′=a−k 原方程可化为 f [ k ∗ v [ i ] + b ] = m a x ( f [ k ′ ∗ w [ i ] + b ] − k ′ ∗ w [ i ] + a ∗ w [ i ] ) f[k*v[i]+b]=max(f[k'*w[i]+b]-k'*w[i]+a*w[i]) f[k∗v[i]+b]=max(f[k′∗w[i]+b]−k′∗w[i]+a∗w[i]) 观察式子， a ∗ w [ i ] a*w[i] a∗w[i]是不变的，而 f [ k ′ ∗ w [ i ] + b ] − k ′ ∗ w [ i ] f[k'*w[i]+b]-k'*w[i] f[k′∗w[i]+b]−k′∗w[i]可以看成 k ′ k' k′的函数。 所以， F ( a ) = m i n { F ( k ′ ) } + a ∗ w [ i ] F(a)=min{F(k')}+a*w[i] F(a)=min{ F(k′)}+a∗w[i] 经典的单调队列优化，解决此问题。 时间复杂度： O ( n C ) O(nC) O(nC)

前三讲背包综合

01，完全，多重背包的混合？ 将困难的问题转化成一个个简单的问题。 判断出哪些物品归属01/完全/多重背包即可。

这3类背包的综合应用题实际上是很多的。

二维费用背包问题

对于物品i，有两种类型的代价，选择物品i的时候，同时要花费这两种代价。 f [ i ] [ u ] [ v ] = m a x { f [ i − 1 ] [ u ] [ v ] , f [ i − 1 ] [ u − c 1 [ i ] ] [ v − c 2 [ i ] ] + w [ i ] } f[i][u][v]=max{f[i-1][u][v],f[i-1][u-c_1[i]][v-c_2[i]]+w[i]} f[i][u][v]=max{ f[i−1][u][v],f[i−1][u−c1​[i]][v−c2​[i]]+w[i]} 可以将空间的复杂度优化一下。 f [ u ] [ v ] = m a x { f [ u ] [ v ] , f [ u − c 1 [ i ] ] [ v − c 2 [ i ] ] + w [ i ] } f[u][v]=max{f[u][v],f[u-c_1[i]][v-c_2[i]]+w[i]} f[u][v]=max{ f[u][v],f[u−c1​[i]][v−c2​[i]]+w[i]}

挖掘题目隐含条件

二维费用，这种条件在题目中会被很隐含地给出来。 看这道例题。 TOJ3596 有N张光盘，每张光盘有一个价钱 c [ i ] c[i] c[i]，现在要从N张光盘中买M张，预算为L，每张光盘有一个快乐值 w [ i ] w[i] w[i]，要求在不超过预算并且恰好买M张，使得快乐值最大。 如果只问不超过m张，那么很好办。 但是如果同时要满足买M张，那么必须开多一维。 题目中有一个隐含的条件：购买的光盘数量是第二维代价。（每张光盘的代价为1） f [ u ] [ v ] = m i n ( f [ u ] [ v ] , f [ u − 1 ] [ v − c [ i ] ] + w [ i ] ) f[u][v]=min(f[u][v],f[u-1][v-c[i]]+w[i]) f[u][v]=min(f[u][v],f[u−1][v−c[i]]+w[i])

涉及复整数域的问题

问题 背包的容量和物品的费用都是复整数。 跟一维背包没有太大区别，只不过同时维护两维信息罢了。 换句话说，只不过是数域发生了改变，其他什么的没有变化。

思想

增加一维状态满足新限制。

分组背包

问题：有n件物品，背包容量为C。 第i件物品体积为 v [ i ] v[i] v[i]，利益为 w [ i ] w[i] w[i] 将n件物品分为K组，每组物品最多选一件。 求所装物品的体积和不超过C的情况下，最大价值和。

解题思路

每组选0件还是选1件。 所以可以得出式子 f [ k ] [ j ] = m a x ( f [ k − 1 ] [ j ] , f [ k − 1 ] [ j − v [ i ] ] + w [ i ] ∣ i ∈ 第 k 组 物 品 ) f[k][j]=max(f[k-1][j],f[k-1][j-v[i]]+w[i]|i∈第k组物品) f[k][j]=max(f[k−1][j],f[k−1][j−v[i]]+w[i]∣i∈第k组物品) 如果空间需要优化，那么关于花费的状态需倒序枚举。 优化后的伪代码：

还有优化？ 如果 w [ i ] ≤ w [ j ] , v [ i ] ≥ v [ j ] w[i]≤w[j],v[i]≥v[j] w[i]≤w[j],v[i]≥v[j]，显然将物品 j j j删除。 时间复杂度： O ( V + N ) O(V+N) O(V+N) V是总体积。N是物品个数。 去掉log的方法，就是计数排序（桶排） 提示：体积为 v 1 v_1 v1​中，价值最大的物品是已知的。

依赖性背包问题

原条件跟背包问题前3讲差不多。 只不过增加了一个条件。 选择了物品i，需要先选择物品j。 NOIP2006金明的预算方案 选择一个主件，每个主件可以选择若干个附件。 问题该向哪个方向转化？ 转化为分组背包问题。 依照什么分组？ 每个主件可以选择它的附件，这些附件随便选。（设主件k有a[k]个附件） 对于主件k，有 2 a [ k ] 2^{a[k]} 2a[k]种选择方案，每种选择方案可以看作是一件物品。 这些物品是同一组的，所以用分组背包解决。 问题来了。 每组的物品很多。 考虑将物品的数量变为 O ( V ) O(V) O(V)个。用 O ( V + N ) O(V+N) O(V+N)的去重方法即可。 然后复杂度变成 O ( n V ) O(nV) O(nV)了。 和图的联系： 相当于一片森林，深度的最大值为1。（根深度为0） 如果深度的最大值>1，那么问题该如何解决？ 此时引入第8讲，泛化物品的概念。 问题会在后文给出答案。

泛化物品

一个物品，无固定的费用与价值。 它的价值随它被分配的费用而变化 从特殊到一般的思想 01背包，完全背包，多重背包就是一些特殊的情况。 物品i的价值是一个函数 h i ( v ) h_i(v) hi​(v) 01中背包物品i的函数： h i ( v ) = { w [ i ] v=v[i] 0 others h_i(v)= begin{cases} w[i]& ext{v=v[i]}\ 0& ext{others} end{cases} hi​(v)={ w[i]0​v=v[i]others​ 多重背包的物品i的函数 h i ( v ) = w [ i ] ∗ v , v ∈ [ 0 , m [ i ] ] h_i(v)=w[i]*v,v∈[0,m[i]] hi​(v)=w[i]∗v,v∈[0,m[i]] 完全背包的物品i的函数 h i ( v ) = w [ i ] ∗ v , v ∈ [ 0 , ⌊ C v [ i ] ⌋ ] h_i(v)=w[i]*v,v∈[0,lfloorfrac{C}{v[i]} floor] hi​(v)=w[i]∗v,v∈[0,⌊v[i]C​⌋] 一个泛化物品组h，它的价值用函数表示如下： h ( v ) h(v) h(v)为体积为v的物品的最大价值。 如果这些物品的体积都没有v，则 h ( v ) = 0 h(v)=0 h(v)=0

泛化物品的DP

目标：求解一个泛化物品f的关于物品体积的函数 f ( v ) f(v) f(v) 如果f是泛化物品f1与f2的和，则 f ( v ) = m a x { f 1 ( v 1 ) + f 2 ( v − v 1 ) } , v 1 ∈ [ 0 , v ] f(v)=max{f1(v_1)+f2(v-v_1)},v_1∈[0,v] f(v)=max{ f1(v1​)+f2(v−v1​)},v1​∈[0,v]

总而言之，可以通过一系列的泛化物品的加和操作，得到最终问题的解。 在《背包九讲2.0》中，有这么一句好话： 一个背包问题中，可能会给出很多条件，包括每种物品的费用、价值等属性，物品之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品。 我的理解： 物品的定义已由特殊到一般。泛化物品已经能够表示所有的物品，这个过程相当于给物品一个新的定义。

泛化物品的DP，最关键的步骤

通过DP来合并出一个新的泛化物品。与**DP的最优子结构**有很大的联系：通过DP来使得目前代表泛化物品的函数记录着最优值。 ### 回到之前的问题 如果深度的最大值>1，那么问题该如何解决？ （也就是附件也有它的附件集合） 显然动用树形背包。 处理父节点的信息之前，就应该处理好它子树的信息。 换句话说，泛化物品x就是它的子树的泛化物品之和。 问题来了。复杂度怎么优化。这种赤裸裸的算法是f[i][j]=max{f[i+1][j-v[x]]+w[x],f[i+siz[x]][j]}。 其中，x是DFS序中第i个元素。 这样就能够O(n^2)解决问题了。 推荐做如下的一道题目：[请转此处](https://blog.csdn.net/Psaily/article/details/81951022) 这就是树形依赖背包的一个最简单的版本。 ## 一些变式 将变式问题特意分出一个单元来讲。 ### 变式0 求解最多可以放多少件物品。 解法很显然。 ### 变式1 求具体方案。 解法原理：需要求出每一个状态f[i][v]究竟从何处转移过来。 （DP状态之间的转移关系可以看成是一个DAG） 以01背包为例，f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 判断f[i][v]的值是等式右边的2个值的哪一个即可。

空间优化后，可以写如下写法： 设 g [ v ] [ 0 ] g[v][0] g[v][0]表示 v − c [ g [ v ] [ 1 ] ] v-c[g[v][1]] v−c[g[v][1]]， g [ v ] [ 1 ] g[v][1] g[v][1]表示最后装了哪个物品，使得背包容积变成 v v v。

变式2

字典序最小 也就是说，需要给出 1.. n 1..n 1..n号物品中求出最优解，且字典序最小。 先举01背包为例。 考虑目前处理的问题是什么 设目前需要解决的问题是 s o l v e ( V , 1.. n ) solve(V,1..n) solve(V,1..n) 假设最优解中含有1号物品，那么问题转化成 s o l v e ( V − c 1 , 2.. n ) solve(V-c_1,2..n) solve(V−c1​,2..n) 否则，问题转化成 s o l v e ( V , 2.. n ) solve(V,2..n) solve(V,2..n). 所以，问题的解决方案就是按照编号从n~1，转变式1。 完全背包，多重背包也是一样的解法。

小结变式1和2

虽然这里只给出了01背包的具体例子，但是其他背包的变式1、2的类似解法也是很好实现的。 抓住重点即可。 ①弄清楚现在要解决什么问题，即 s o l v e ( 状 态 ) solve(状态) solve(状态) ②需要求出每一个状态 f [ i ] [ v ] f[i][v] f[i][v]究竟从何处转移过来。

变式3

与计数式DP结合。 还是那句老话，需要求出每一个状态 f [ i ] [ v ] f[i][v] f[i][v]究竟从何处转移过来。 只要明确了这一点，那么转移的时候，判断一下就好了。

变式4

求第k优解。 时间复杂度： O ( V N K ) O(VNK) O(VNK) 我目前解决的一个求第k优解的问题，就是求第K短路。这道题目用A*解决。 最关键的部分在哪里？ 选完最优的，剩下的最优解即为第2优的， 以此类推下去，做k次就能够得到第k优解。 核心思想：合并方程时同时维护好前k优的解。 就以多重背包为例，(由于太弱了，所以只会 O ( V ∗ ∑ l o g ( m [ i ] ) ∗ K ) O(V*sum log(m[i])*K) O(V∗∑log(m[i])∗K)的解法) 对于下面的式子，请注意：物品有 ∑ l o g ( m [ i ] ) sum log(m[i]) ∑log(m[i])个，而不是 n n n个。 多重背包的DP方程: f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − c [ i ] ] + w [ i ] ) f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]) f[i][j]=max(f[i−1][j],f[i−1][j−c[i]]+w[i]) 设 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]表示做到第i个物品（加了二进制优化之后），第k优的值。 相当于现在有2k个候选值，选出k个来。 这2k个候选值就是: f [ i − 1 ] [ j ] [ 1… k ] , g [ i − 1 ] [ j − c [ i ] ] [ 1.. k ] f[i-1][j][1…k],g[i-1][j-c[i]][1..k] f[i−1][j][1...k],g[i−1][j−c[i]][1..k]和 g [ i − 1 ] [ j − c [ i ] ] [ k ] = f [ i − 1 ] [ j − c [ i ] ] [ k ] + w [ i ] g[i-1][j-c[i]][k]=f[i-1][j-c[i]][k]+w[i] g[i−1][j−c[i]][k]=f[i−1][j−c[i]][k]+w[i] 选出k个，只需要 O ( k ) O(k) O(k)的复杂度。 一般人不会这么无聊，所以k一般不会很大。 毒瘤题：求严格第k优的解的个数… 谁会啊？

①背包问题的内容很多。由背包问题引申出来的DP问题数不胜数。 ②通过背包问题，更应该受到其中的一些思想、各种各样的解法的启发，从而运用到日常的DP练习。 ③需要整理思想、各种各样的解法的巧妙原理，将他们联系起来。