单调队列优化多重背包
请不要禁用脚本，否则网页无法正常加载 单调队列优化多重背包
little_prince · 2020-01-26 16:49:48 · 个人记录
（这是个很考验细节的优化，因为明白了思路不一定自己会写出来，代码细节比较多）
这种优化虽然说可能常数比二进制优化的多重背包大，也难写，时间复杂度降低的相对于二进制优化来说不是特别多，但可以非常好的体现单调队列优化的精妙之处。
先来看这样一个表格：
j-4v[i] j-3v[i] j-2v[i] j-v[i] jj-5v[i] j-4v[i] j-3v[i] j-2v[i] j-v[i]
通过这个表格，是不是发现了如果考虑当前物体i，每次更新体积v[i]的倍数（这里表述不是很准确，但大致是那个意思）,有单调的可能？ 没错，我们就以这个倍数作为下标放入单调队列中来优化。
现在回头看一下普通的O（nm∑c[i]）的转移方程，发现可利用单调队列优化的性质就比较明显了： f[j] = max(f[j],f[j - k v[i]] + k w[i]）（姑且略去条件）
所以，我们的步骤是：
1.设定余数u，从0~v[i]-1循环；
2.由u得到分成的倍数段p，maxp = int（（m-u）/ v[i]），p从maxp到0循环。（结合多重背包的性质想一想，为什么要倒序循环？）
3.状态转移方程：f[u + p v[i]]=max{f[u + p v[i]],f[u + k v[i]] + (p-k) w[i]}.其中p-c[i] <= k <= p-1.
好，以上是思路，接下来是代码细节，我直接在代码中说明。思路要清晰哟！
#include<bits/stdc++.h> using namespace std; inline int read(){ int f=1,r=0;char c=getchar(); while(!isdigit(c)){if(c=='-') f=-1;c=getchar();} while(isdigit(c)){r=r*10+c-'0';c=getchar();} return f*r; } int n,m,f[20007],w[1007],v[1007],c[1007],q[20007]; int calc(int i,int u,int k){ return f[u + k * v[i]] - k * w[i]; } int main(){ n = read();m = read(); for(int i = 1;i <= n; i++) { v[i] = read();w[i] = read();c[i] = read(); for(int u = 0;u <= v[i]-1; u++) { int maxp = (m-u) / v[i]; int head = 1,tail = 0;//阶段是p，u,对于每一个u，我们进行单调队列优化， //每一个u都不会互相影响，都用的上一个阶段的f[j]进行的转移，所以这层循环的复杂度为O（m），算法总复杂度为O(nm) //1.利用单调队列预处理出转移的决策，可想象为先向队列里头装决策，才便于后面队列的滚动 //注意，这里的队列是一个决策坐标单调递减，决策值单调递减（队头最优）的单调队列，所以注意循环顺序哦 for(int k = maxp;k >= max(maxp - c[i],0); k--) { while(head <= tail && calc(i,u,q[tail]) <= calc(i,u,k)) tail--; q[++tail] = k; } //2.预处理好了就可以更新，并让单调队列滚动起来啦 for(int p = maxp;p >= 0; p--) { while(head <= tail && q[head] > p-1) head++; if(head <= tail) //再次强调这里的细节，队列非空才可转移啊！ f[u + p * v[i]] = max(f[u + p * v[i]], calc(i,u,q[head]) + p * w[i]); //更新完了，下面加入新决策（如果不能理解可以认为，加入新决策的原因是有了c[i]的限制，所以要滚动起来 if(p - c[i] - 1 >= 0)//同样的，别让队列滚过了头哦 { while(head <= tail && calc(i,u,q[tail]) <= calc(i,u,p-c[i]-1)) tail--; q[++tail] = p - c[i] - 1; } } } } //最后的更新答案 int ans = 0; for(int i = 1;i <= m; i++) ans = max(ans,f[i]); cerr<<"ans = ";cout<<ans<<endl; return 0; //恭喜你学会啦！ }让自律成为自己的一种生活方式。
2025-08-22 18:39 点击量：2