Acwing 6. 多重背包问题 III

单调队列优化法

从公式入手来看是否还有可以改进的地方

(dp[i][j] = max(dp[i - 1][j],dp[i-1][j - v] + w,dp[i-1][j -2 * v] + 2*w,...,dp[i-1][j-s_i*v]+s_i*w))

我们可以发现该方程的第二维是 (j-v,j-2*v,j-3*v,j-s_i*v) ，因为受到完全背包的感染，所以写以下(dp[i][j-v])的方程来对比看一下。

从图中可以看出来，可以看出来一开始是匹配的，但是最后一个不匹配，也就是 (j) 没有 (j-v) 的最后一项，所以

虽然猜想不对，但是我们发现了 (dp[i][j]) 对比 (dp[i][j-v]) 的方程中间有一大部分是匹配的，而且是后面少一项和前面多一项的关系，想利用这一部分，就想到了一个非常匹配这个过程的方法--------滑动窗格。

为了方便表述，我们这里使用滚动数组，将 (dp[i -1][j]) 的值全部存在(pre)数组里面。(pre[j] = dp[i-1][j])

(pre[j]) 的含义是从前 (i-1) 个物品中选，且体积不超过 (j) 的最大价值。

那么假设 (s_i)==3，(dp[i][j] = max(pre[j],pre[j-v]+w,pre[j-2*v]+2*w,pre[j-3*v]+3*w))

可以看出来，当前的窗格需要从前面往后推,然后边推还可以边把 (dp[i][j - v],dp[i][j-?*v])全给赋值了，然后可以发现以下两点

• 不能像暴力法那样，直接丢掉一维，不然你求 (j-5*v) 的时候，要用到 (j-6*v) 已经被覆盖掉了，所以用一个滚动数组 (pre) 来存储

• 因为前往后推，所以我们先要找到起点的体积比如说上图就是 (j-6*v) ,假设 (0<j-6*v<v)。

起点有 0 到 (v-1) 种可能，那么我们这里就可以换一种写法了比如说

上面是具体的写法，下面将其抽象化：总体积 (m = k*v+j，0<j<v),先不管后面加的部分

写到这里，我们发现，其实我们枚举 (0<j<v) 然后一直推到这个(j) 对应的结尾就可以完成这个物品的更新了。这里补全一下抽象化后的整个表示

然后现在知道怎么更新，还知道怎么全部都更新，剩下的就是怎么快速的找到滑动窗格的最大值，那么单调队列登场。

另起一个数组为 (q[N]) ，里面存的是背包的体积，设置队列头为 (head) ,尾巴为 (tail) (q[头, , , ,...,尾巴]) ,保证队列里面是单调的，也就是 (head) 代表的体积的价值 (ge tail) 代表的体积的价值。

现在问题来到怎么维护单调队列的单调性?

当前的背包体积 (k)，因为要单调队列的单调性，所以要找到一个合适的位置讲当前背包放入队列中，这个合适的位置的体积的最大价值大于体积k的最大价值才行，(pre[q[tail]]) 取得的就是当前尾部体积的价值相当于(dp[i - 1][q[tail]]) 和当前的价值 (dp[i-1][k]) 比较，有没有发现什么不对劲？

(pre[j])的含义是从前(i-1)个物品中选，且体积不超过(j)的最大价值。(pre[h] = dp[i-1][h])

(dp[i][j] = max(dp[i - 1][j],dp[i-1][j - v] + w,...,dp[i-1][j-s_i*v]+s_i*w))

看了眼原始方程，回忆下变量的含义。没错漏掉了(k - q[tail])这部分给(dp[i - 1][q[tail]])带来的价值，所以比较的时候要给加回去继续比较，那么就可以写出这部分的代码了

可以对比起来看一下

while (head <= tail && pre[q[tail]] + (k - q[tail]) / v * w <= pre[k])
             tail--;

时间复杂度：

(O(物品数列*背包体积)=O(N*V))

实现：

接下来直接看完整代码就可以了：

#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20005;
// pre存储i - 1的时候的值
// q为偏移量为?时候的单调队列
int dp[N], pre[N], q[N], n, m;
int main()
{
    //n为物品的总数，背包容量为m
    scanf("%d%d", &n, &m);
    while (n--)
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);

        //赋值上一层结果
        memcpy(pre, dp, sizeof(dp));

        //枚举偏移量(起点)
        for (int i = 0; i < v; i++)
        {
            //建新的单调队列 头>>>尾巴，里面存的是体积
            int head = 0, tail = -1;

            //更新该起点代表的行,k是此时的体积
            for (int k = i; k <= m; k += v)
            {
                //判断窗格是否超过了k,头需要往后滑动
                if (head <= tail && k - q[head] > s * v)
                    head++;

                //赋值
                //pre[q[head]]+(k - q[head]) / v * w)：前i-1个中选，且体积不大于q[head]的最大价值 + 第i个物品选(k - q[head]) / v 个的价值
                if (head <= tail)
                    dp[k] = max(dp[k], pre[q[head]] + (k - q[head]) / v * w);

                //队列中加入k,并且维护队列单调性
                //pre[k]：前i-1个中选，且体积不大于q[head]的最大价值 + 第i个物品选0个
                //pre[q[tail]] + (k - q[tail]) / v * w ：前i-1个中选，且体积不大于q[tail]的最大价值 + 第i个物品选(k - q[tail]) / v个
                while (head <= tail && pre[q[tail]] + (k - q[tail]) / v * w < pre[k])
                    tail--;
                q[++tail] = k;
            }
        }
    }
    printf("%d", dp[m]);
    return 0;
}