背包

快乐的MQK · 2020-07-11 10:56:03 · 个人记录

背包九讲

一：

1. 多重背包问题（单调队列优化模板）

以余数来划分阶段

2. 混合背包问题：将对应的物品的类型按照对应的类型转移方程即可。例如：一个物品只能取一次，则采用 01 背包的倒叙转移方程。

3. 二位费用背包问题：再增加一维状态即可，设 f[i][v][u] 表示前i件物品付出两种代价分别为v和u时可获得的最大价值。

4. 分组背包模板

5. 金明的预算方案（有依赖的背包模板）

二：

1. 输出方案，不管顺序。记录下每个状态的最优值是由状态转移方程的哪一项推出来的。

方程：f[i][v]=max\{f[i-1][v],f[i-1][v-c[i]]+w[i]\}
设 g[i][v]=0 表示推出 f[i][v] 的值时是采用了方程的前一项（也即 f[i][v]=f[i-1][v] ），g[i][v]=1 表示采用了方程的后一项,输出时倒叙输出，V 的值不断减小，判断一下是否选当前 i 即可。

2. 输出方案，字典序最小。

背包问题求具体方案（字典序最小）

以 01 背包为例：将所有数据输入后，因为正常的 01 背包是倒叙的，又因为要求的是最小的字典序，所以要将整个过程倒过来，将所有的物品从 n ~ 1， 包括体积也应该从 0 ~ m 的顺序来写动规。

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

最后输出时，从 1 ~ n 来循环判断，当 f[i][j]=f[i+1][j-v[i]]+w[i] 时，应输出当前的 i 值， vol-=v[i]。（vol 为剩余的体积）

3. 求方案总数：得到装满背包或将背包装至某一指定容量的方案总数，不要求得到最大的价值。

方程：f[i][v]=sum\{f[i-1][v],f[i][v-c[i]]\} 初始条件：f[0][0]=1

4. 最优方案的总数

最优方案：指物品总价值最大的方案。

以 01 背包为例，使用一维数组来写。

背包问题求方案数

求出装新物品时的总价值，与不装新物品时作对比。

如果装新物品的方案总价值更大，那么用 f[j-v]+w 来更新 f[j]，用 cnt[j-v] 更新 cnt[j]

如果总价值相等，那么最大价值的方案数就多了 cnt[j-v] 种。

5. 求次优解、第 K 优解

其基本思想是将每个状态都表示成有序队列，将状态转移方程中的 max/min 转化成有序队列的合并。

设 f[i][v][k]表示前 i 个物品、背包大小为 v 时，第 K 优解的值。

有序队列 f[i-1][v] 即 ①f[i-1][v][1..K]，f[i-1][v-c[i]]+w[i] 则理解为在 ②f[i-1][v-c[i]][1..K] 的每个数上加上 w[i] 后得到的有序队列。

合并①②这两个有序队列并将结果的前 K 项储存到 f[i][v][1..K] 中的复杂度是 O(K)。最后的答案是 f[N][V][K]。