多重背包（单调队列优化）

发表于 更新于

前言

多重背包问题的时间复杂度为 O(nm2)，复杂度很高，所以我们需要将其优化。其中一种办法就是使用单调队列优化，可以使复杂度达到 O(nm)。

单调队列

单调队列的一个元素有两个值：元素的值和位置（下标），单调队列会保证队首元素是原数列中值最小（或最大）的。单调队列的作用可以看下面的模板题：
P1886 滑动窗口 /【模板】单调队列
有一个长为 n 的序列 a，以及一个大小为 k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
了解了单调队列的用途，我们以样例为例来看它如何实现。STL中的双端队列可以实现单调队列，但是常数不得不说有一点大，所以一般单调队列都用手写队列来实现。
1 3 -1 -3 5 3 6 7
首先定义两个队列 p 与 q（也可以定义结构体队列），p 中是每个元素在原数列的位置，q 中是每个元素的值。
(1) 将 1 入队，q=1,p=1，此时队首元素为 1；
(2) 将 3 入队，由于 3>1，所以 q=1,3,p=1,2，此时队首元素为 1；
(3) 将 −1 入队，由于 −1<3,−1<1，所以 1 和 3 都出队，q=−1,p=3，此时队首元素为 −1；
(4) 将 −3 入队，同理 −3<−1，所以将 −1 出队，此时q=−3,p=4，队首元素为 −3；
(5) 将 5 入队，此时q=−3,5,p=4,5，队首元素为 −3；
(6) 将 3 入队，由于 3<5，所以q=−3,3,p=4,6，队首元素为 −3；
(7) 将 6 入队，由于 4⩽7−3，也就是 −3 已经不在窗口中了，所以弹出 −3 ，此时q=3,6,p=6,7，队首元素为 3；
(8) 将 7 入队，此时q=3,6,7,p=6,7,8，队首元素为 3；
可以观察到每一次操作的队首元素都是当前窗口中的最小值（除了(1)(2)，因为此时已经入队的元素个数少于窗口大小）。我们可以简单总结以下这些操作：设元素总数为 n，窗口大小为 m，对于一个即将入队的元素 xi ，如果队尾元素满足 xi<qback，那么弹出队尾元素，如果队首元素对应的在原数列中的位置 pfront⩽i−m，那么弹出队首元素，然后将 xi 加入到 q 的队尾，i 加入到 p 的队尾，如果 xi⩾m，则队首元素就是当前窗口中的最小元素。
同理，我们也可以推出最大值的求法。下面上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
using namespace std;
int n,m,a[1000001],q[1000001],p[1000001],T,R;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }
    T=0,R=-1;
    for(int i=1;i<=n;++i)
    {
        while(T<=R&&p[T]<=i-m) ++T;
        while(T<=R&&q[R]>a[i]) --R;
        q[++R]=a[i];
        p[R]=i;
        if(i>=m) printf("%d ",q[T]);
    }
    printf("\n");
    T=0,R=-1;
    for(int i=1;i<=n;++i)
    {
        while(T<=R&&p[T]<=i-m) ++T;
        while(T<=R&&q[R]<a[i]) --R;
        q[++R]=a[i];
        p[R]=i;
        if(i>=m) printf("%d ",q[T]);
    }
    return 0;
}

单调队列优化多重背包

单调队列如何能和背包扯上关系的？设这件物品体积为 v，价值为 w，数量为k，我们来看一下多重背包的状态转移方程：
f[m]=max(f[m],f[m−v]+w,f[m−2×v]+2×w,f[m−3×v]+3×w,⋯)
将 m 换为其他数，我们就可以得到：
f[j]=f[j]
f[j+v]=max(f[j]+w,f[j+v])
f[j+2×v]=max(f[j]+2×w,f[j+v]+w,f[j+2×v])
f[j+3×v]=max(f[j]+3×w,f[j+v]+2×w,f[j+2×v]+w,f[j+3×v])
稍加转换，可得：
f[j+0×v]=max(f[j])
f[j+1×v]=max(f[j],f[j+v]−w)+w
f[j+2×v]=max(f[j],f[j+v]−w,f[j+2×v]−2×w)+2×w
f[j+3×v]=max(f[j],f[j+v]−w,f[j+2×v]−2×w,f[j+3×v]−3×w)+3×w
是不是惊人的相似。
这样就可以得到：
f[j+k×v]=max(f[j],f[j+v]−w,f[j+2×v]−2×w,f[j+3×v]−3×w,⋯,f[j+k×v]−k×w)+k×w
我们就可以看成有一个大小为 k的窗口在数列上扫过，每一个状态对应一个窗口。这样这个问题就成功地转换成了单调队列的问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
using namespace std;
int n,m,q[1000001],p[1000001],T=-1,R=0,f[100001];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        int a,b,c;
        scanf("%d%d%d",&b,&a,&c);
        for(int j=0;j<a;++j)
        {
            T=0;
            R=-1;
            for(int k=j;k<=m;k+=a)
            {
                while(T<=R&&k-p[T]>a*c) ++T;
                while(T<=R&&q[R]+(k-p[R])/a*b<=f[k]) --R;
                p[++R]=k;
                q[R]=f[k];
                f[k]=q[T]+(k-p[T])/a*b;
            }
        }
    }
    printf("%d",f[m]);
    return 0;
}
相关文章