0%

多重背包单调队列优化

多重背包问题:有 $n$ 种物品,每种物品有一个重量 $v_i$,价值 $w_i$,数量 $a_i$,问一个重量为 $m$ 的背包最多能装多少价值的物品。

我们很容易就能写出一个 $O(nm\sum a_i)$ 的 DP 方程:

如何优化这个式子呢?

注意到对于每一个 $j$,其能够转移的 $f$ 的下标是一个关于模 $v_i$ 的剩余类,于是我们可以按照模 $v_i$ 分类转移。

这样分类后,我们要求的就是某个余数中最大的 $f$,并且注意到能够更新当前 $f[j]$ 的下标是单调的,于是可以使用单调队列优化。

但是对于不同的 $k$,其贡献也不同。如何处理这个问题呢?我们把 $j$ 写成 $j=p\times v_i + r$ 的形式,然后改写一下 DP 方程:

这样就使得 $\max$ 内的值只与 $p-k$ 有关了。至于 $p-k$ 具体是多少我们并不关心,因为我们很容易就能确定它的范围:只需要保证查询时的下标 $\geq j - a_i\times v_i$ 即可。

在插入时将 $f[j]-p\times w_i$ 放入单调队列中,查询时查询单调队列里下标 $\geq j - a_i\times v_i$ 的值再加上 $p \times w_i$ 来更新 $f[j]$,我们就在 $O(nm)$ 的时间内解决了多重背包问题。

代码:等用到的时候再写吧。。