最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

有 $n(0\lt n \le 1000)$ 种物品和一个容量为 $V(0\lt V \le 20000)$ 的背包

第 $i$ 种物品最多有 $s_i(0\lt s_i \le 20000)$ 件，每件体积是 $v_i(0\lt v_i \le 20000)$，价值是 $w_i(0\lt w_i \le 20000)$

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大

多重背包—单调队列优化

对于 多重背包 分析，以及 二进制优化 这里不做额外讲解，直接分析 单调队列 优化方式

关于 多重背包【朴素版】 可以看这篇博客

多重背包的原始状态转移方程

$$ f(i,j) = \max\big(f(i-1,j), f(i-1,j-v)+w, \cdots, f(i-1,j-sv)+sw\big) $$

考虑用完全背包的优化方式来优化这个方程

$$ f(i,j-v) = \max\big(f(i-1,j-v), f(i-1,j-2v)+w, \cdots, f(i-1,j-(s+1)v)+(s)w\big) $$

写出这个公式好像并不是那么管用

因为 完全背包 是一口气把所有体积全部用掉，即
$$ \max(a,b,c,d) = \max\big(a,\max(b,c,d)\big) $$

然而 多重背包 对于每个物品的个数是有限制的，导致我们最终的等式是如下样子：
$$ \max(a,b,c,d) \ne \max\big(a,\max(b,c,d,e)\big) $$

但是，我们可以把这个式子 继续 推导下去，直到背包体积被用到不能再用为止
$$ \begin{cases} f(i,j) = \max\big(f(i-1,j), f(i-1,j-v)+w, \cdots, f(i-1,j-sv)+sw\big) \\\ \\\ f(i,j-v) = \max\big(f(i-1,j-v), f(i-1,j-2v)+w, \cdots, f(i-1,j-(s+1)v)+sw\big) \\\ \\\ f(i,j-2v) = \max\big(f(i-1,j-2v), f(i-1,j-3v)+w, \cdots, f(i-1,j-(s+2)v)+sw\big) \\\ \\\ \cdots \\\ \\\ f(i,r+sv) = \max\big(f(i-1,r+sv), f(i-1,r+(s-1)v)+w, \cdots, f(i-1,r)+sw\big) \\\ \\\ f(i,r+(s-1)v) = \max\big(f(i-1,r+(s-1)v), \cdots, f(i-1,r)+(s-1)w\big) \\\ \\\ \cdots \\\ \\\ f(i,r+2v) = \max\big(f(i-1,r+2v), f(i-1,r+v)+w, f(i-1,r)+2w\big)\\\ \\\ f(i,r+v) = \max\big(f(i-1,r+v), f(i-1,r)+w\big)\\\ \\\ f(i,r) = f(i-1,r)\\\ \\\ \end{cases} $$

其中 $r = j \mod v_i$，也可以理解为 完全背包 下把当前物品 选到不能再选 后，剩下的 余数

得到 $f(i,r) = f(i-1,r)$ 后，我们再利用 完全背包优化思路 往回倒推一遍

会惊奇的发现一个 滑动窗口求最大值 的模型，具体如下：

为了方便大家观察，我们把 $f(i-1,j)$ 改写成 $f_j$

$$ \begin{cases} f(i,r) = f_r\\\ \\\ f(i,r+v) = \max\bigg(f_{r+v}, f_r+w\bigg)\\\ \\\ f(i,r+2v) = \max\bigg(f_{r+2v}, f_{r+v}+w, f_{r}+2w\bigg)\\\ \\\ \cdots \\\ \\\ f(i,r+(s-1)v) = \max\bigg(f_{r+(s-1)v},f_{r+(s-2)v}+w, \cdots, f_r+(s-1)w\bigg) \\\ \\\ f(i,r+sv) = \max\bigg(f_{r+sv}, f_{r+(s-1)v}+w, \cdots, f_r+sw\bigg) \quad (滑动窗口已满)\\\ \\\ f(i,r+(s+1)v) = \max\bigg(f_{r+(s+1)v}, f_{r+sv}+w, \cdots, f_{r+v}+sw\bigg) \quad (滑动窗口已满)\\\ \\\ \cdots \\\ \\\ f(i,j-2v) = \max\bigg(f_{j-2v}, f_{j-3v}+w, \cdots, f_{j-(s+2)v}+sw\bigg) \quad (滑动窗口已满) \\\ \\\ f(i,j-v) = \max\bigg(f_{j-v}, f_{j-2v}+w, \cdots, f_{j-(s+1)v}+sw\big) \quad (滑动窗口已满) \\\ \\\ f(i,j) = \max\bigg(f_j, f_{j-v}+w, \cdots, f_{j-sv}+sw\big) \quad (滑动窗口已满) \\\ \\\ \end{cases} $$

可能看上去还是有点复杂，为了再方便大家观察，我们去掉 $w$，然后把数组展开成一条链

具体如下图：

于是通过该 滑动窗口 ，我们就能在 线性 的时间里求出 i 阶段里，所有满足 $j \equiv r \mod (v)$ 的 $f(i,j)$

滑动窗口 求 最大值 的实现，只需利用 队列 在队头维护一个 最大值 的 单调递减 的 单调队列 即可

为了更新所有 i 阶段里的状态 $f(i,j)$ ，我们只需再额外枚举所有的 余数 $r$ 即可

不要忘记，滑动窗口内部比较最大值的时候，有一个在之前为了方便观察，被我删掉的偏移量 w

要记得加上再比较

具体就是 当前下标 和该 最大值的下标 之间差了 $x$ 个 $v$，那么就要加上 $x$ 个 $w$

在上面公式里，还是比较容易看出的吧，就不做额外的推导了

Code（二维朴素版）

写这个代码是为了方便大家理解

时间复杂度：$O(n \times v)$

空间复杂度：$O(n \times v)$

滑动窗口的长度为 $s_i+1$

#include <iostream>

using namespace std;

const int N = 1010, M = 20010;

int n, m;
int v[N], w[N], s[N];
int f[N][M];
int q[M];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; ++ i)
    {
        for (int r = 0; r < v[i]; ++ r)
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v[i])
            {
                while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++ ;
                while (hh <= tt && f[i - 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[i - 1][j]) -- tt;
                q[ ++ tt] = j;
                f[i][j] = f[i - 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

Code（一维优化）

时间复杂度：$O(n \times v)$

空间复杂度：$O(v)$

和 01背包 的优化类似，观察到 状态转移方程，对于 i 阶段，只会用到 i-1 层的状态

因此可以采用 拷贝数组 或 滚动数组 的写法

拷贝数组写法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 20010;

int n, m;
int v[N], w[N], s[N];
int f[M], g[M];
int q[M];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; ++ i)
    {
        memcpy(g, f, sizeof g);
        for (int r = 0; r < v[i]; ++ r)
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v[i])
            {
                while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++ ;
                while (hh <= tt && g[q[tt]] + (j - q[tt]) / v[i] * w[i] <= g[j]) -- tt;
                q[ ++ tt] = j;
                f[j] = g[q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

滚动数组写法

#include <iostream>

using namespace std;

const int N = 1010, M = 20010;

int n, m;
int v[N], w[N], s[N];
int f[2][M];
int q[M];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; ++ i)
    {
        for (int r = 0; r < v[i]; ++ r)
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v[i])
            {
                while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++ ;
                while (hh <= tt && f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[(i - 1) & 1][j]) -- tt;
                q[ ++ tt] = j;
                f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout << f[n & 1][m] << endl;
    return 0;
}