单调队列优化多重背包

0 前置芝士

• 背包DP

• 多重背包

• 单调队列

1 多重背包问题

多重背包问题说的是:假设现在有 $n$ 件物品和一个容量大小为 $m$ 的背包,第 $i$ 件物品的体积为 $v_i$ ,价值为 $w_i$,并且第 $i$ 件物品只有 $s_i$ 件,现在要选择这些物品中的一些装进背包,请最大化背包里的物品价值总和.

一般的,如果不加任何的优化,那么我们可以令 $f_i$ 表示当背包容量为 $i$ 时,所能获得的最大价值.状态转移方程为:

$$f_j=max\{f_j,f_{i-k\times v_i}+k\times w_i\}$$

此时,若 $i,j,k$ 同阶,那么总时间复杂度为 $O(n^3)$.

这种做法但凡数据稍微大一点就会T掉,因此我们考虑进行优化.

主要的优化方式有两种,第一种是二进制分组,第二种就是单调队列优化.这里我们主要介绍一下单调队列优化.

2 单调队列

单调队列是一种数据结构,主要用于处理滑动窗口问题,可以在 $O(n)$ 的时间内处理出每个窗口的最值等信息.

我们可以考虑对状态转移方程进行变形,然后套用单调队列进行优化.

3 优化

首先,优化的第一步,我们要先将状态分组.

具体来讲,就是把状态按照对 $v_i$ 进行取模的余数进行分组.也就是吧状态分成