在某些题目中,我们需要一个可行性背包,并且需要支持删除某个物品,这个时候我们就可以用到可行性转方案数背包的小技巧。
说人话,这个转换就是把 \(\text{bool}\) 类型的背包转换成 \(\text{int}\) 类型的方案数背包,这样做有什么用呢?
首先 \(\text{bool}\) 类型的 DP 显然是不支持删除的,如果每次都重新 DP 一次,单次复杂度是 \(O(nV)\) 的,太慢了。
那么转换成方案数背包我们就会有一个容斥的做法,具体来说,设我们要删除的物品大小为 \(w\),删除前的背包为 \(g_i\),删除后的背包为 \(f_i\),我们可以预处理出 \(g_i\),再利用 \(g_i\) 求出 \(f_i\),我们可以分类讨论得出这个转移:
\[f_i=
\left\{
\begin{aligned}
& g_i &,0 \le i < w\\
& g_i-f_{i-w} &,w \le i \le n
\end{aligned}
\right.
\]
解释一下 \(f_{i-w}\) 的含义:\(i-w\) 的容量中不选 \(w\),剩下的容量选了一个 \(w\),所以指示了 \(g_i\) 中选了 \(w\) 的部分,正是我们需要减掉的部分。单次删除复杂度为 \(O(V)\)。