$\Huge\color{orchid}{点击此处获取更多干货}$

单调队列法

一般实现和二进制拆分都是将多重背包问题转化为了0-1背包问题来解决，但是单调队列法不转化为0-1背包问题。那么，让我们回到最初的定义上，独属于多重背包问题的状态转移关系：

到这儿，很有可能会有人在想，能不能用完全背包问题的方式来代替表示。这里虽然在有限的状态下，不能完全替代，但是如果忽略数量限制，只要还能装下就一直往背包里装，以此来逐步限制背包的最大占用容量$j$，那么可以得到下面的递推式组：
（由于第$i$轮迭代中所有的状态都一定是从第$i-1$轮迭代的状态中得出的，故下面的递推式组中，$dp$表示第$i$轮，$last$表示第$i-1$轮）
$$\begin{cases}dp(j) = max\{last(j),last(j-v)+w,last(j-2*v)+2*w,…,last(j-s*v)+s*w\} \\dp(j-v) = max\{last(j-v),last(j-2*v)+w,last(j-3*v)+2*w,…,last(j-(s+1)*v)+s*w\} \\dp(j-2*v) = max\{last(j-2*v),last(j-3*v)+w,…,last(j-(s+2)*v)+s*w \\...... \\dp(r+s*v) = max\{last(r+s*v),last(r+(s-1)*v)+w,last(r+(s-2)*v)+2*w,…,last(r)+s*w\} \\dp(r+(s-1)*v) = max\{last(r+(s-1)*v),last(r+(s-2)*v)+w,…,last(r)+(s-1)*w\} \\...... \\dp(r+2*v) = max\{last(r+2*v),last(r+v)+w,last(r)+2*w\} \\dp(r+v) = max\{last(r+v),last(r)+v\} \\dp(r)=last(r)\end{cases}.$$

其中$r=j\%v$，相当于将当前物品最大限度装入后，背包无法利用的剩余空间。仔细对比可以发现，每一个$max$函数中，值最多的不会超过$(s+1)$个，并且它们都是相对连续的状态值，这点就跟滑动窗口最值问题很像了。下图给出了可视化描述：（分两部分，黑色表示窗口未满，红色表示窗口已满，绿色表示窗口最终状态）

将它转化为滑动窗口最大值问题之后，在第$i$轮迭代中，所有模$v$同余的$j$代表的状态都可以一次性求解出。因此在当前迭代中，只需要枚举所有可能的$r=j\%v$即可。

C++ 代码

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

deque<int> q;                               //单调队列，存放容量状态j

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int* dp = new int[m + 1](),
        * last = new int[m + 1];                //dp和last对应i轮和i-1轮
    int v, w, s;
    for (int i = 0; i < n; i++) {
        cin >> v >> w >> s;
        for (int r = 0; r < v; r++) {           //枚举余数r
            q.clear();                          //每个余数对应的状态序列不一样，要清空单调队列
            for (int j = r; j <= m; j += v) {   //从r滑动到m，窗口长为s+1
                dp[j] = last[j];                //先默认不选，然后开始选
                if (!q.empty() 
                    && q.front() < j - s * v) { //队头的最大值滑出去了要移除
                    q.pop_front();
                }
                while (!q.empty() 
                    && last[q.back()] - (q.back() - r) / v * w <= last[j] - (j - r) / v * w) {
                    q.pop_back();               //队尾更小的值要出队
                }
                q.push_back(j);
                if (!q.empty()) {               //取队头，用队头更新当前的j（可以保证以小推大）
                    dp[j] = max(dp[j], last[q.front()] + (j - q.front()) / v * w);
                }
                //单调队列中的元素全都可以保证模v同余，因此不用担心除得浮点数
            }
        }
    }
    cout << dp[m] << endl;
    delete[] dp, last;
    return 0;
}

备注

单调队列法用了deque来实现，但是考虑到deque的时间常数比较大，如果主办方实在“不干人事”，连使用deque的都要恶心他们到底，那么可以利用一下其中的隐含条件，就是由于$v$最小是1，单调队列的大小最多也就是$m+1$，则可以$\text{new[]}$一条长度为$m+1$的数组$q$，然后参照之前“顺序队列”的实现方法，用$\text{head,tail}$索引指向队头队尾，然后将两索引都置于头端以代替$\text{clear}$，这样应该可以省不少时间（记得最后$\text{delete[]}$哟）