zl程序教程

您现在的位置是:首页 >  工具

当前栏目

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

学习 问题 通俗易懂 背包 小记 九讲
2023-06-13 09:12:33 时间

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

前言

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

原目录(大致意思)

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件。

for i=1 to n
    for j=C to v[i]
        f[j]=max(f[j-v[i]]+w[i])

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

对于完全背包(无限背包) 每个物品有无限件。 实际上每件物品最多只有 ⌊ C v [ i ] ⌋ \lfloor\frac{C}{v[i]}\rfloor ⌊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 ] ⌋ \lfloor\frac{C}{v[i]}\rfloor ⌊v[i]C​⌋转化为二进制。 比如 ⌊ C v [ i ] ⌋ = 13 \lfloor\frac{C}{v[i]}\rfloor=13 ⌊v[i]C​⌋=13,拆成 1 , 4 , 8 1,4,8 1,4,8 则问题转化为01背包。 这个优化使效率提高了不少。 优化③ 将代码改为:

for i=1 to n
    for j=v[i] to C
        f[j]=max(f[j-v[i]]+w[i])

为什么对? 因为j正着循环,考虑了物品i放 [ 1 , ⌊ C v [ i ] ⌋ ] [1,\lfloor\frac{C}{v[i]}\rfloor] [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]\geq\lfloor\frac{C}{v[i]}\rfloor 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/完全/多重背包即可。

for i=1 to n
    if 第i件物品∈01背包 ...
    else
    if 第i件物品∈完全背包 ...
    else
    if 第i件物品∈多重背包 ...

这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组物品) 如果空间需要优化,那么关于花费的状态需倒序枚举。 优化后的伪代码:

for k=1 to K
    for j=C downto min(v[i],i∈第k组)
        for i∈第k组
            f[j]=max(f[k-1][j],f[k-1][j-v[i]]+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删除。 时间复杂度: 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]& \text{v=v[i]}\\ 0& \text{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,\lfloor\frac{C}{v[i]}\rfloor] 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。

i=n;
v=V';
while(v){
    选择物品g[v][1]
    v=g[v][0];
}

变式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练习。 ③需要整理思想、各种各样的解法的巧妙原理,将他们联系起来。

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/158191.html原文链接:https://javaforall.cn