背包模型（三）

根题

AcWing 2. 01背包问题

01背包问题：每种物品选或不选两种选择

• 状态表示
• 集合 f[i, j] :所有只从前 $i$ 个物品中选，且总体积不超过 $j$ 的选法的集合
• 属性：Max/Min/Count
• 状态计算
• 集合划分
  • 选择第 $i$ 个物品的所有方案
  • 不选择第 $i$ 个物品的所有方案
  • 划分依据：用“最后一步”来划分（要确保有区分度）
• 转移方程
  • 不选择第 $i$ 个物品：f[i - 1][j]
  • 选择第 $i$ 个物品：f[i - 1][j - v[i]] + w[i]

AcWing 3. 完全背包问题

完全背包问题：每种物品选0个、1个、2个……无穷个

• 状态表示
• 集合 f[i, j] :所有只从前 $i$ 个物品中选，且总体积不超过 $j$ 的选法的集合
• 属性：Max/Min/Count
• 状态计算
• 集合划分
  • 第 $i$ 个物品选0个、1个、2个、……、s个（$s\times v_{i}\leq j$）
• 转移方程：f[i, j] = max(f[i - 1, j], f[i,j - v[i]] + w[i])
  • 推导：

当空间优化为一维之后，只有完全背包问题的体积是从小到大循环的

AcWing 4. 多重背包问题

多重背包问题：每种物品选0个、1个、2个、……、s[i] 个

AcWing 5. 多重背包问题 II

多重背包问题的二进制优化，时间复杂度为 $O(N\times \log s\times V)$

AcWing 9. 分组背包问题

有 $n$ 组物品，每组物品里有若干物品，每组物品中只能选一个物品

对第 $i$ 组物品，不选、选第一个、选第二个……

转移方程：f[i,j]=max(f[i-1,j],f[i-1,j-v[i,1]]+w[i,1],f[i-1,j-v[i,2]]+w[i,2],……,f[i-1,j-v[i,s[i]]]+w[i,s[i]])

基础课笔记

AcWing 6. 多重背包问题 III

单调队列：AcWing 154. 滑动窗口

在完全背包的优化里，求 f[i,j] 的 max(f[i-1,j],……) ，省略号里的最大值可以用 f[i,j-v] 代替。而在多重背包里，由于 f[i,j-v] 最后多出了一项，因此无法用完全背包优化的方法来优化多重背包

但是在不考虑体积不够用的情况下，我们观察省略号里的内容，发现 f[i,j] f[i,j-v] f[i,j-2v] …… 都需要求 $s$ 项式子中的最大值

假设 j % v == r ,则以 $r$ 为起点，在数轴上标记 $r,r+v,r+2v,……,j-v,j$ 。求 f[j] 时，需要求 f[j-v,j-2v,……,j-sv] 加上各自偏移量的最大值；求 f[j-v] 时，需要求 f[j-2v,j-3v,……,j-(s+1)v] 的最大值。用一个窗口把这 $s$ 项在数轴上框出来，发现窗口是逐项滑动的。因此多重背包的优化就是一个滑动窗口模型

画出数轴后，还可以发现，完全背包问题是求坐标前所有前缀的最大值，因此只需要一个变量去维护某一段前缀就可以了；而多重背包是求前一段的最大值，需要用队列维护

维护单调队列时，需要删除没有用的元素。因为元素大小的比较需要加上偏移量，所以比较时也需要满足偏移量的要求。

这里采用的是减去相应的偏移量处理来比较大小（也可以采用加上相应的偏移量来比较，大小的比较是相对的）

while(hh <= tt && g[q[tt]] + (k - q[tt]) / v * w <= g[k]) tt --;    //这是加法
while(hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt --;    //这是减法。两者都可

时间复杂度：$O(N\times V)$ （单调队列维护的平均时间复杂度是 $O(1)$ 的）

6代码

代码里维护的队列长度是 $s + 1$

AcWing 7. 混合背包问题

AcWing 8. 二维费用的背包问题

二维费用的背包问题可以和01背包、完全背包、多重背包结合在一起

闫氏DP分析法

• 状态表示 f[i, j, k]
• 集合:所有只从前 $i$ 个物品中选，且总体积不超过 $j$ ,总重量不超过 $k$ 的选法
• 属性：Max
• 状态计算
• 集合划分(本题和01背包结合)
  • 不选第 $i$ 个物品：f[i - 1,j,k]
  • 选第 $i$ 个物品：f[i - 1,j - v[i],k - m[i]] + w[i]
• 转移方程: f[i,j,k]=max(f[i-1,j,k],f[i-1,j-v[i],k-m[i]]+w[i])
  • 可以优化成一维：f[j,k]=max(f[j,k],f[j-v[i],k-m[i]]+w[i])

8代码

AcWing 10. 有依赖的背包问题

树形DP：AcWing 285. 没有上司的舞会

可能还要复习一下图的存储

AcWing 11. 背包问题求方案数

AcWing 12. 背包问题求具体方案

可以与01、完全、多重、分组结合。这里以01为例

• 01背包转移方程：f[i,j]=max(f[i-1,j],f[i-1,j-v[i]]+w[i])
• 求方案就是看每个状态是从哪个状态转移过来的。对应的是最短路问题中的求路径
• 同最短路中求路径，由于求路径与求最短距离是相反的顺序，因此如果要求从起点到终点的最短路径，则在求最短距离时需要从终点开始遍历到起点。同理，背包问题的遍历就要从第 $n$ 的物品遍历到第 $1$ 个物品求属性，再从 $1$ 到 $n$ 求方案
• 题目中如果要求输出字典序最小的答案，就要判断每个物品是否选择时中贪心
  • 只能选：必选
  • 只能不选：必不选
  • 可选可不选：一定要选
    • 因为背包问题是按字典序从小到大遍历每个物品，如果不选，则该方案的字典序一定闭选的字典序大
• 由于在求方案时需要用到 i-1 i+1 的数据，因此不能简化维数
• 另一种做法是开一个数组 g[i,j] 记录该状态是由哪个状态转移过来的，同LIS中输出最长上升子序列

12代码

衍生题

AcWing 1013. 机器分配

分组背包问题+求具体方案

$n$ 个公司对应 $n$ 组；给公司分配机器 $1台、2台、3台、……、m台$ 对应该组里的 $m$ 个物品；每个物品的体积就是分配的台数，价值就是能提供的盈利

求具体方案，则 $i$ 从 $n$ 到 $1$ 遍历，找到每个状态是由哪个状态转移过来的

1013代码

AcWing 487. 金明的预算方案

分组背包问题

分组背包问题的本质是为对每个组里的物品进行决策——选或不选，且每个组里的物品决策是互斥的，只能选择一个物品。能转化成该模型的题目都可以用分组背包来解决

本题转化为分组背包问题的思路是，对于一个主件，给其买附件的选择只能有一种。比如一个主件有两个附件 $a,b$ ,那买附件的选择就是不买、买 $a$ ，买 $b$ ，买 $ab$ 。这四种选择只能选择一种。因此对于每个主件的决策就可以构成一组背包，每个决策就是该组里的物品，每组中只能拿一个物品。因此本问题就是分组背包问题。

要注意，本题中价值的表达要看题目的定义。主件和附件的存储要考虑。枚举对每个主件买附件的决策时使用了二进制优化

487代码

AcWing 426. 开心的金明

简单的01背包问题，确实是开心的金明 :smile:

426代码