模板及讲解

大部分文字来自背包九讲。

完全背包问题

有$ N $种物品和一个容量为$ V $的背包，每种物品都有无限件可用。放入第$ i $种物品的费用是$ C_i $，价值是$ W_i $。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

基本方程

令$ F [i, v] $表示前$ i $种物品恰放入一个容量为$ v $的背包的最大权值。
$F [i, v] = max(F [i − 1, v − kC_i] + kW_i |0 ≤ kC_i ≤ v)$

转化 01 背包

把第$ i $种物品拆成费用为$ C_i2^k$、价值为$ W_i2^k $的若干件物品$(C_i2^k ≤ V)$
这是二进制的思想。因为，不管最优策略选几件第$ i $种物品，其件数写成二进制后，总可以表示成若干个$ 2^k $件物品的和。这样一来就把每种物品拆成$ O(log ⌊V /Ci⌋) $件物品
然后可以运用这些物品做 01 背包。

O(VN) 算法

$F [i, v] = max(F [i − 1, v], F [i, v − C_i] + W_i)$

多重背包问题

有$N$种物品和一个容量为$V $的背包。第$i$种物品最多有$M_i$件可用，每件耗费的空间是$C_i$，价值是$W_i$。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

基本方程

令$F [i, v]$表示前$i$种物品恰放入一个容量为$v$的背包的最大价值
$F [i, v] = max(F [i − 1, v − kC_i] + kW_i | 0 ≤ k ≤ M_i)$

转化 01 背包

把每个物品拆成带权$2^0,2^1,2^2,……,2^{k-1},M_i-2^k+1$的物品，然后做 01 背包即可。

O(VN) 算法

单调队列优化

混合三种背包问题

for (int i = 1; i <= n; i++) {
  if (i 是 01 背包) 做 01 背包; 
  else if (i 是 完全背包) 做完全背包;
  else if (i 是 多重背包) 做多重背包;
}

分组背包

基本方程

解决什么问题

每组之间独立，每组只选一个。
那么如果我们做 01 背包时发现有物品不止一个值，并且这个值可以全部暴力算出来，那么我们可以暴力算出来一个物品所有取值，然后分组地取。

例题：CF 946D

意思就是逃课。怎样逃课才能使得最后上完课的时间减去最开始的上课的时间最短。这里是按$0$和$1$来代表有没有课，$1$代表有课，可以逃。但是最多只能逃$k$节课。

发现可以 DP，但是真心不会转移怎么办？我们看每天，逃不同数量的课有不同的收益。所以我们把一天看成一组，预处理逃不同数量的课有不同的收益，做一个分组背包即可。