记录一下这道经典题。

按某知名 AI 的说法，这个并没有那么难，所以讲一种简单点的理解方法。

首先，多重背包的状态转移方程是：

f[i][j] = max(f[i][j - 1], f[i - 1][j - k * v[i] + k * w[i])

这个方程中只用到了前一行的数，所以我们可以将其变成滚动数组的模式：

f[j] = max{f[j - k * v[i]] + k * w[i]}

好了，我们来看一下这个方程有什么性质。发现：

选 $k$ 个该物品时，体积变化是 $k*v$，只有同余数组的容量之间才会相互影响。

所以想到按余数分组。

枚举一个余数 $r$，显然有 $j = r + m * v$ （余数的定义），还有我们只用到了这一组的 $v,w,s$ 所以可以边输入边处理。

所以状态转移方程可以变为：

f[j] = max{f[r + m * v - k * v] + k * w}

设 $t = m - k$，则有：

f[j] = max{f[r + t * v] + (m - t) * w}（t ≥ m-s）

拆开括号：

f[j] = max{f[r + t * v] + m * v - t * v}（t ≥ m-s）

因为 $m * v$ 是不变的，所以可以扔到外面去：

f[j] = max{f[r + t * v] - t * v} + m * v

现在只需找到窗口 $t ∈ [m-s, m]$ 内的最大值，再统一加上 $m * v$。

然后计算滑动窗口即可。

简单说明一下滑动窗口的思想：

1.如果你的算法跟不上时代了，那你就要退役了。
2.如果有一个人，比你小还比你巨，那你就要退役了。

时间复杂度与 $0/1$ 背包同级。

代码：

#include <bits/stdc++.h>
using namespace std;

const int M = 20005;

int f[M], g[M], n, m, q[M];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        memcpy(g, f, sizeof(f));//把上一行的存下来 
        for (int r = 0; r < v; r ++ )//余数 
        {
            int head = 0, tail = -1;//滑动窗口 
            for (int k = 0; ; k ++ )
            {
                int j = r + k * v;
                if (j > m) break;
                //如果你的算法跟不上时代了，那你就要退役了
                while (head <= tail && q[head] < k - s) head ++ ;
                if (head <= tail)
                {
                    //选最小的更新 
                    int t = q[head];
                    f[j] = max(g[j], g[r + t * v] + (k - t) * w);
                }
                //如果有一个人，比你小还比你巨，那你就要退役了
                while (head <= tail && (g[j] - k * w >= g[r + q[tail] * v] - q[tail] * w)) tail -- ;
                q[ ++ tail] = k;//加入窗口 
            }
        }
    }
    printf("%d\n", f[m]);
    return 0;
}