单调队列优化多重背包

· · 个人记录

单调队列优化 dp 一般用于决策集合上下界均单调变化，每个决策在候选集合均插入或删除至多一次的问题。且转移方程中的每一项可拆为仅与阶段（状态）有关或仅与决策有关。这样不会影响单调队列中的有序性。

多重背包 f[j] 由 f[j-k*v[i]] k\in cnt[i] 转移而来。i 为阶段，即枚举到的第几类物品，v[i] 是物品体积，cnt[i] 为这一类物品有多少个。

我们尝试将 j 改变一，看看它决策集合的变化。发现和原来决策集合没有交集，仅仅是平移了一位，即 f[j-k*v[i]-1]。但如果将 j 改变 v[i]，发现和原来的决策集合大部分重合，仅仅进入一个新决策，弹出一个旧决策（不考虑边界）。这启发我们按照模 v[i] 的余数对 j 进行分类计算，将 j 拆为 u+p*v[i]，这样可以达到用单调队列优化的效果。

朴素的代码：

for (int i = 1; i <= n; i++){ //阶段，枚举到第几类物品 
        for (int u = 0; u < v[i]; u++){ //枚举余数 
            for (int p = (m-u)/v[i]; p >= 0; p--){ 
            //因为枚举的当前容量 j = u+p*v[i] 满足 0 <= u+p*v[i] <= m 
            //所以 p*v[i] <= m-u。p <= (m-u)/v[i] 
            //由于不能重复转移，采用倒序枚举 
                for (int k = p-c[i]; k <= p-1; k++){
                    //j 由 k*v[i]+u 转移来，c为每类物品的的物品个数
                    int j = u+v[i]*p;
                    int j_ = u+v[i]*k;
                    f[j] = max(f[j],f[_j]+(p-k)*w[i]); // w[i] 为物品价值
                }

            }
        } 
    }

从上面的程序上可以容易看出，在 i,u 不变时， k 的上下界是单调变化的。而方程转移式 f[u+v[i]*k]+(p-k)*w[i] 可以把 p 分离出去，从而达到只和 k 有关。可以用单调队列进行优化，只用维护单调递减队列，存放 f[u+v[i]*k]-k*w[i] 这个信息。滑动的窗口是 [p-c[i],p-1]。每次取单调队列队头就是最大值，来更新答案。

改成单调队列优化思路和朴素 dp 其实一样。我这里写的是先把初始的候选集合插入队列。之后每次队列中只插入一个值。

int calc(int i,int u, int k){
    return f[u+k*v[i]]-k*w[i];
}
int main(){
    for (int i = 1; i <= n; i++){ //阶段，枚举到第几类物品 
        for (int u = 0; u < v[i]; u++){ //枚举余数 
            int l = 1, r = 0;
            int maxp = (m-u)/v[i];
            for (int k = maxp-1; k >= max(maxp-c[i],0); k--){ // 初始的决策集合
                while(l <= r && calc(i,u,q[r]) <= calc(i,u,k)) r--;
                q[++r] = k;
            }
            for (int p = maxp; p >= 0; p--){
                while(l <= r && q[l] > p-1) l++;   //排除过时决策
                f[u+p*v[i]] = max(f[u+p*v[i]], calc(i,u,q[l])+p*w[i]);//拿队头更新答案（把p*w[i]分离出来了）
                if (p-c[i]-1 >= 0){//边界条件，是否加入新决策。注意这里含零。 
                    while(l <= r && calc(i,u,q[r] <= calc(i,u,p-c[i]-1))//踢出队尾比值它小年龄还比它大的 
                    q[++r] = p-c[i]-1; 
                }
            }
        } 
    } 
}