思路

多重背包每种物品可以选择多个（有上限）。将思路转化一下，多重背包可以等价变换为01背包，即把多个数量的同种物品也看成是多个不同种类的物品，那么就可以用01背包的解法来做题了。

当然结果毫无疑问超时。好在题目有提示，可以采用二进制优化或者单调队列优化。

说明：看这篇题解之前，请先完全理解01背包问题，其中的dp数组用的是一维数组。如果你还在用二维数组，那么请先理解了一维数组再来看。

二进制优化

假设某种物品的数量为1000件，拆分成1000种不同类型的物品当然也可以计算，但是时间过久。一种好的办法是将之拆分成10个种类，每个种类分别包含1、2、4、8、16、32、64、128、256、489件。

为什么这么拆分呢？首先不看最后一个数字489，我们看前9个数字，都是2的乘方，并且9个数字任意选择“取”或“不取”就可以构成0-511的所有数字。再加上最后的489，就能表示0-1000的所有数字了。

按照这种思路对多重背包的所有物品进行拆分，转化成01背包问题，即可求解。动态规划的转移方程会自动帮我们筛选可能的组合方式，从而快速获取最大的价值数。

单调队列优化

首先看下多重背包的状态转移方程，其中 k = min(s, j / w)。

dp[j] = max(dp[j] , dp[j - w] + v , dp[j - 2 * w] + 2 * v, ... , dp[j - k * w] + k * v)。

对于每一个j都要做这样的计算，时间复杂度是不可接受的，因此必须想办法优化。观察这个式子，可以发现每一个d[j]只跟与它相隔w倍数的元素相关。很明显j，j - w，j - 2 * w，...，j - k * w都是对w同余的。既然如此，可以对dp的所有元素按照余数分组，每一组使用单调队列进行计算。（注：也可以用优先队列，但是需要考虑更复杂，时间复杂度也会增加。）

这样做的好处是，当计算dp[j]时，只需要和队首的元素进行比较即可，而不需要再比较所有k个元素。

到了这一步可能很多人理解起来比较困难，我尽量解释的通俗易懂。

对于w的每个余数r（0 <= r < w），我使用一个双端队列辅助计算，队列的每个元素包含两个值，{ k，dp[k] }。

step1：首先将{ r，dp[r] }加入队列。

step2：遍历后续每一个和 r 同余的数字 j 。比较 j 和队列队首的k相差几个w，如果超过s个，则将队首元素出队。

step3：将{ j，dp[j] }添加到队列末尾，不过由于我们要保证队列是单调的，因此添加之前要先进行比较。假设队尾元素是{ k，dp[k] }，那么如果dp[k] + (j - k) / w * v <= dp[j]，就应该将队尾元素出队。重复这一步直到队列为空或者队尾元素不再出队，再将{ j，dp[j] }添加到队列末尾。此刻添加的dp[j]可能会对后续的dp[j + k * w]产生优化。

step4：可以对dp[j]进行状态转移了，将其和队首元素{ k，dp[k] }进行比较。dp[j] = max(dp[j] , dp[k] + (j - k) / w * v)。

接下来重复上述step 2、3、4直至循环结束即可。

可以看到，虽然名义上用的是单调队列，但其实{ k，dp[k] }中的dp[k]并不单调，而是计算后的修正值单调，因此不能使用优先队列，如果要用就得做更复杂的转换。

c++代码

下面代码同时包含二进制优化和单调队列优化，注意要AC的话考虑w和v为0的情况，并使用long long。

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

int main() {
    int T, n, m;
    long long w, v, s;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        vector<long long> dp(m + 1, 0);//dp[i]表示背包容量为i时的最大价值
        for (int i = 0; i < n; ++i) {
            cin >> w >> v >> s;
            if (v == 0) continue;
            if (w == 0) {
                v *= s;
                for (auto& p : dp) {
                    p += v;
                }
            } else {
                //二进制优化01背包
                for (int k = 1; k <= s; k <<= 1) {
                    long long vv = k * v;
                    long long ww = k * w;
                    for (int j = m; j >= ww; --j) {
                        dp[j] = max(dp[j], dp[j - ww] + vv);
                    }
                    s -= k;
                }
                if (s) {
                    long long vv = s * v;
                    long long ww = s * w;
                    for (int j = m; j >= ww; --j) {
                        dp[j] = max(dp[j], dp[j - ww] + vv);
                    }
                }
                continue;
                //单调队列优化
                int disJ = w * s;
                for (int r = 0; r < w; ++r) { //同余
                    deque<pair<int, long long>> q;
                    q.emplace_back(r, dp[r]);
                    for (int j = r + w; j <= m; j += w) {
                        if (!q.empty() && j - q.front().first > disJ) q.pop_front();
                        while (!q.empty() && q.back().second + (j - q.back().first ) / w * v <= dp[j])
                            q.pop_back();
                        q.emplace_back(j, dp[j]);
                        dp[j] = max(dp[j], q.front().second + (j - q.front().first) / w * v);
                    }
                }
            }
        }
        cout << dp[m] << endl;
    }
}