基于单调队列的多重背包优化

这里是简介

1.1 前言

​ 多重背包,想必看到这篇博文的人应该都知道了,这里仅仅列出伪代码($n$为物品个数,$m$为背包容积)

for i := 1 to N
    for j := 0 to M
        for k := 0 to c[i]
            f[i][j] = max(f[i - 1][j - k * v[i]] + k * w[i])

​ 显然,这种算法的复杂度是很不可取的,于是我们来考虑优化

1.2 优化方式

​ 设$c,v,w$分别为当前物品的个数,体积,价值,根据原始转移方程可知,$f_i$一定是由$f_{i-1}$转移而来,所以$c,v,w$不用开数组(有的$OJ$竟然会卡空间…),为了方便说明,以下设数组$g$表示数组$f_{i-1}$,于是方程简化为:

f[j] = max(g[j - k * v] + k * w) //0≤k≤c

​ 显然,就算不简化,我们也能看出:$f_j$只从$f_{j-v_i},f_{j-v_i\times 2}…f_{j-v_i\times c}$转移过来,且对于每一个这其中的$j$,都有如下性质:它们模上$v$后的余数相同,于是我们将其模$v$后的余数拎出来考虑,循环可以这样写:

for i := 1 to N
    for j := 0 to v - 1
        ...

​ 接下来呢,就要枚举系数$k$了

for (k = 0; k * v + j <= M; ++k)

​ 你不觉得枚举系数很麻烦吗?这样就好了

for (k = j; k <= M; k += v)

​ 接下来来看转移方程,根据之前得出的转移方程,显然我们是要找到在一个长度为$c$的区间内最大的$g[j - k \times v] + k\times w$,可以用单调队列来存储,于是又有

while (l <= r && (k - q[l]) / v >= c) ++l;
while (l <= r && f[i - 1][k] - f[i - 1][q[r]] >= (k - q[r]) / v * w) --r;
q[++r] = k; 
f[i][k] = f[i - 1][q[l]] + (k - q[l]) / v * w;
  • 这里的$(k-q_i)/v$代表两个数的系数相差多少,$+1$后则代表所跨区间的长度,这里的$(k - q[l]) / v \geq c$用于防止区间长度大于$c$,相当于$(k - q[l]) / v + 1 > c$,不满足条件则弹出队首元素。
  • 当在队列中插入新元素时,需有$g[k]+k/v\times w \geq g[q[r]]+q[r]/v\times w$,这是根据单调队列所存储元素的定义得出的,移项后得$g[k]-g[q[r]]>=(k-q[r])/v\times w$,巧妙地避免了余数的问题。
  • 我们只插入$k$就好了,不然不方便$\Delta w$的计算。
  • 这里取队首再加上$\Delta w=(k-q[l])/v\times w$就好了

1.3 代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 1e3 + 10, M = 1e4 + 10;
int n, m, f[N][M], v, w, c, q[M], l, r, ans;

int main () {
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf ("%d%d%d", &c, &v, &w);
        c = min (c, m / v);
        for (int j = 0; j < v; ++j) {
                l = 1; r = 0;
            for (int k = j; k <= m; k += v) {
                while (l <= r && (k - q[l]) / v >= c) ++l;
                while (l <= r && f[i - 1][k] - f[i - 1][q[r]] >= (k - q[r]) / v * w) --r;
                q[++r] = k;
                f[i][k] = f[i - 1][q[l]] + (k - q[l]) / v * w;
            }
        }
    }
    for (int i = 1; i <= m; ++i)
        ans = max (ans, f[n][i]);
    printf ("%d\n", ans);
    return 0;
}

1.4 注意

  1. 单调队列初始化为$l=1,r=0$,且在循环$j$内初始化
  2. 单调队列长度开到$M$,因为有可能出现$v=1$的情况
  3. 最后答案不一定存在$f_{n,m}​$里面,要在$1…m​$扫一遍
  4. 一定要记得$c=min(c,m/v)$,为了防止背包溢出