单调队列优化多重背包
本篇的重点在于单调队列优化,如果您还没学过朴素做法和二进制分组,推荐先学习前置知识:多重背包
本文中,物品种类为$n$,背包总体积为$V$,每种物品有$s_i$个。
朴素做法
最朴素的做法就是把s个物品当成不同的来存储,这样的时间复杂度就是$O(n * S * V), S = \sum s_i$
可以用于解决$10^2$范围内的问题
二进制分组优化
我们知道对$k$个物品来说,他们的$v_i, w_i$都是一样的,所以选择谁并没有先后关系的差距,只有选择数量的差距,那么我们可以对$k$进行二进制的拆分(从低向高),然后做0-1背包。(显然拆分后的几组通过不同的合并构成小于等于$k$的任何一个的,这里就不过多赘述)
这样的复杂度是$O(n * V * log_2S)$
单调队列优化
我们知道dp转移方程是:$dp[i][j] = max(dp[i - 1][j - k*v[i]] + k*w[i])$
我们可以得知,转移方程的更新不是连续的,而是以$v[i]$为单位
所以我们可以根据余数的不同,可以将状态划分为$[0, v_i - 1]$,一共$v_i$种。
那么对于每一种状态,我们都可以采取上面相同的状态转移方程。
单调队列就是在这个转移的过程中使用的。
(为了方便理解,我先贴一下代码)
#define rep(i, st, ed) for(int i = st;i < ed; i ++ )// 如果对您阅读造成障碍,非常抱歉,建议先将这个define手动改回for循环
rep(i, 1, n + 1) {
cin >> v[i] >> w[i] >> s[i];
rep(j, 0, v[i]) {
deque<int> q;
q.clear();
for(int k = j;k <= V;k += v[i]) {
dp[1][k] = dp[0][k];
if(q.size() && q.front() < k - s[i] * v[i]) q.pop_front();// 队头超过范围,弹出
if(q.size()) dp[1][k] = max(dp[1][k], dp[0][q.front()] + (k - q.front()) / v[i] * w[i]);
while(q.size() && dp[0][q.back()] + (k - q.back())/v[i] * w[i] <= dp[0][k]) q.pop_back();// 如果后面更优,请读者自行理解为什么要这么判断“更优”
q.push_back(k);
}
}
rep(j, 0, V + 1) dp[0][j] = dp[1][j];
}
在第二层循环中,我们对每一种状态都进行后续的转移(当然,这个转移也是以$v_i$为单位的)。
因为我们最多能用$s_i$个物品,而且对于每次转移,我们都期望直接$O(1)$得到最大值,这就非常符合滑动窗口的本质(区间最值+区间长度限制)。
所以我们就可以采取单调队列的方式完成状态转移,最终时间复杂度$O(n * V)$
对于单调不下降的判断
有这么一行dp[0][q.back()] + (k - q.back())/v[i] * w[i] <= dp[0][k]
其本质就是,将队列中前面的状态进行填充,填充到k,看和当前的k相比,哪个更优,显然,如果队列中的元素大的话,在窗口限制之内,选择原本队列的元素是更优的。