背包 DP 进阶
背包相关 trick
泛化物品的背包
这种背包,单个物品 \(i\) 没有固定的费用和价值,它的价值是随着分配给它的费用而定.在背包容量为 \(V\) 的背包问题中,当分配给物品 \(i\) 的费用为 \(v_i\) 时,能得到的价值就是 \(h_i\left(v_i\right)\).
那么,我们枚举分配给第 \(i\) 个物品的重量 \(w'\),这时的物品价值将会是 \(h_i(w')\),那么现在的价值就是 \(f_{i - 1, w - w'} + h_i(w')\).所以此时状态转移的方程为 \(f_{i, j} = \max \limits_{0 \le k \le j}(f_{i - 1, j - k} + h_i(k))\).实际上上面这一堆东西讲的就是 \((\max, +)\) 卷积.
分组背包
「Luogu P1757」通天之分组背包
有 \(n\) 件物品和一个大小为 \(m\) 的背包,第 \(i\) 个物品的价值为 \(w_i\),体积为 \(v_i\).同时,每个物品属于一个组,同组内最多只能选择一个物品.求背包能装载物品的最大总价值.
这种题其实只是从「在所有物品中选择一件」变成了「从当前组中选择一件」,于是就对每一组进行一次 0-1 背包就可以了.
再说一说如何进行存储.我们可以将 \(t_{k,i}\) 表示第 \(k\) 组的第 \(i\) 件物品的编号是多少,再用 \(\mathit{cnt}_k\) 表示第 \(k\) 组物品有多少个.
实现
1 2 3 4 5 6 7 | |
1 2 3 4 5 6 7 | |
这里要注意:一定不能搞错循环顺序,这样才能保证正确性.
回退背包
普通的 0-1 背包求方案数只需要直接 dp 即可,但是有时会遇到形如「其他物品都能选,只有几个物品不能选」的情况,而且通常是在同一组物品中多次出现不同的物品不能选,比如部分复杂的树上背包.这时直接 dp 可能会 TLE,所以需要引入回退背包来处理这种情况.
注意到背包中物品是无序的:对于两个物品,先放哪个不会当前情况造成任何影响,可以认为 每一个物品都是最后被放入的那个.所以可以先把所有东西的 dp 预处理出来,然后把某一个物品的贡献撤销即可.即:
注意循环时从小到大执行,否则它对应的贡献方式就是完全背包的方式了.
背包杂项
输出方案
输出方案其实就是记录下来背包中的某一个状态是怎么推出来的.我们可以用 \(g_{i,v}\) 表示第 \(i\) 件物品占用空间为 \(v\) 的时候是否选择了此物品.然后在转移时记录是选用了哪一种策略(选或不选).输出时的伪代码:
1 2 3 4 5 6 7 8 9 10 11 | |
求最优方案总数
要求最优方案总数,我们要对 0-1 背包里的 \(\mathit{dp}\) 数组的定义稍作修改,DP 状态 \(f_{i,j}\) 为在只能放前 \(i\) 个物品的情况下,容量为 \(j\) 的背包「正好装满」所能达到的最大总价值.
这样修改之后,每一种 DP 状态都可以用一个 \(g_{i,j}\) 来表示方案数.
\(f_{i,j}\) 表示只考虑前 \(i\) 个物品时背包体积「正好」是 \(j\) 时的最大价值.
\(g_{i,j}\) 表示只考虑前 \(i\) 个物品时背包体积「正好」是 \(j\) 时的方案数.
转移方程:
如果 \(f_{i,j} = f_{i-1,j}\) 且 \(f_{i,j} \neq f_{i-1,j-v}+w\) 说明我们此时不选择把物品放入背包更优,方案数由 \(g_{i-1,j}\) 转移过来,
如果 \(f_{i,j} \neq f_{i-1,j}\) 且 \(f_{i,j} = f_{i-1,j-v}+w\) 说明我们此时选择把物品放入背包更优,方案数由 \(g_{i-1,j-v}\) 转移过来,
如果 \(f_{i,j} = f_{i-1,j}\) 且 \(f_{i,j} = f_{i-1,j-v}+w\) 说明放入或不放入都能取得最优解,方案数由 \(g_{i-1,j}\) 和 \(g_{i-1,j-v}\) 转移过来.
初始条件:
1 2 3 4 5 | |
因为背包体积最大值有可能装不满,所以最优解不一定是 \(f_{m}\).
最后我们通过找到最优解的价值,把 \(g_{j}\) 数组里取到最优解的所有方案数相加即可.
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
背包的第 k 优解
普通的 0-1 背包是要求最优解,在普通的背包 DP 方法上稍作改动,增加一维用于记录当前状态下的前 k 优解,即可得到求 0-1 背包第 \(k\) 优解的算法. 具体来讲:\(f_{i,j,k}\) 记录了前 \(i\) 个物品中,选择的物品总体积为 \(j\) 时,能够得到的第 \(k\) 大的价值和.这个状态可以理解为将普通 0-1 背包只用记录一个数据的 \(f_{i,j}\) 扩展为记录一个有序的优解序列.转移时,普通背包最优解的求法是 \(f_{i,j}=\max(f_{i-1,j},f_{i-1,j-v_i}+w_i)\),现在我们则是要合并 \(f_{i-1,j}\),\(f_{i-1,j-v_i}+w_i\) 这两个大小为 \(k\) 的递减序列,并保留合并后前 \(k\) 大的价值记在 \(f_{i,j}\) 里,这一步利用双指针法,复杂度是 \(O(k)\) 的,整体时间复杂度为 \(O(nmk)\).空间上,此方法与普通背包一样可以压缩掉第一维,复杂度是 \(O(mk)\) 的.
例题 HDU 2639 Bone Collector II
求 0-1 背包的严格第 \(k\) 优解.\(n \leq 100,v \leq 1000,k \leq 30\)
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | |
背包相关问题
混合背包
混合背包就是将 01 背包、完全背包和多重背包混合起来,有的只能取一次,有的能取无限次,有的只能取 \(k\) 次.
这种题目看起来很难,但是每一种物品的选择依然是独立的,因此可以判断当前物品是哪一种背包,然后使用这种背包的解决方案即可.
例题
「Luogu P1833」樱花
有 \(n\) 种樱花树和长度为 \(T\) 的时间,有的樱花树只能看一遍,有的樱花树最多看 \(A_{i}\) 遍,有的樱花树可以看无数遍.每棵樱花树都有一个美学值 \(C_{i}\),求在 \(T\) 的时间内看哪些樱花树能使美学值最高.
核心代码
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
习题:HDU 5410 CRB and His Birthday
二维费用背包
「Luogu P1855」榨取 kkksc03
有 \(n\) 个任务需要完成,完成第 \(i\) 个任务需要花费 \(t_i\) 分钟,产生 \(c_i\) 元的开支.
现在有 \(T\) 分钟时间,\(W\) 元钱来处理这些任务,求最多能完成多少任务.
这道题是很明显的 0-1 背包问题,可是不同的是选一个物品会消耗两种费用(经费、时间),只需在状态中增加一维存放第二种费用即可.这时状态转移方程变为 \(f_{i, j, k} = \max(f_{i - 1, j, k}, f_{i - 1, j - t_i, k - c_i} + w_i)\).本题的 \(w_i\) 均是 \(1\).
这时候就要注意,再开一维存放物品编号就不合适了,因为容易 MLE.
实现
1 2 3 4 5 6 | |
1 2 3 4 | |
有依赖的背包
「Luogu P1064」金明的预算方案
金明有 \(n\) 元钱,想要买 \(m\) 个物品,第 \(i\) 件物品的价格为 \(v_i\),重要度为 \(p_i\).有些物品是从属于某个主件物品的附件,要买这个物品,必须购买它的主件.
目标是让所有购买的物品的 \(v_i \times p_i\) 之和最大.
直接当成 树上背包 处理即可.注意在最后将所有背包合并在一起.
参考资料与注释
本页面最近更新:,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Ir1d, sshwy, StudyingFather, Marcythm, partychicken, H-J-Granger, NachtgeistW, countercurrent-time, Enter-tainer, Tiphereth-A, weiranfu, greyqz, iamtwz, Konano, ksyx, ouuan, paigeman, wolfdan666, AngelKitty, CCXXXI, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, GoodCoder666, Henry-ZHR, HeRaNO, Link-cute, LovelyBuggies, LuoshuiTianyi, Makkiy, mgt, minghu6, odeinjul, oldoldtea, P-Y-Y, PotassiumWings, SamZhangQingChuan, shenshuaijie, Suyun514, weiyong1024, Xeonacid, xyf007, Alisahhh, Alphnia, c-forrest, cbw2007, dhbloo, fps5283, GavinZhengOI, Gesrua, hsfzLZH1, hydingsy, kenlig, kxccc, lychees, Menci, Peanut-Tang, PlanariaIce, sbofgayschool, shawlleyw, Siyuan, SukkaW, TianKong-y, tLLWtG, WAAutoMaton, x4Cx58x54, xk2013, zhb2000, zhufengning, hhc0001
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用