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

原理及一般实现方法

多重背包问题中，可以把有限个数的同种物品放进背包，每一种物品除了之前定义的体积$v$和价值$w$以外，还有一个数量$s$。如果把这样的物品组$\{v,w,s\}$看成相互独立存在的$s$个物品$\{v,w\}$，就可以当作0-1背包问题来解决了。$dp$图表和0-1背包问题几乎一样，就直接给出代码了。

另外，考虑到第$i$个物品的信息只有在第$i$轮迭代时才会用到，所以不用像之前那样用数组事先保存所有的$\{v,w,s\}$，等到第$i$轮迭代的时候，在循环体内执行$\{v,w,s\}$的输入即可

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int* dp = new int[m + 1]();             //new+空括号初始化，全部置为0
    int v, w, s;
    for (int i = 1; i <= n; i++) {
        cin >> v >> w >> s;                 //第i轮迭代时输入{v,w,s}
        while (s--) {                       //看成s个独立的物品，跟0-1背包一样递推
            for (int j = m; j >= v; j++) {
                dp[j] = max(dp[j], dp[j - v] + w);
            }
        }
    }
    cout << dp[m] << endl;
    delete[] dp;
    return 0;
}

小技巧1：二进制拆分法

将$\{v,w,s\}$拆分成$s$个单独的$\{v,w\}$，在计算的时候其实是比较费时的，有一种基于二进制思想的拆分方法，可以将$s$拆分成较少的部分，并且$0\sim s$中的所有数值都可以由拆分出的某些“部分”累加而得。假设正整数$N$满足$\lfloor log_2(N) \rfloor =k$，则将$N$拆分为$(k+1)$个部分，其中的$k$个部分为$2^i(i=0,1,…,k-1)$，对应着二进制中1左移$i$位的真值，这些部分的累加总和是$2^k-1$，即二进制下的$k$个1。如果还有剩余，则将最后的$R=N-2^k+1$另作为一部分。由于任何整数总能拆成若干2的正整数幂项之和，因此$0\sim 2^k-1$的数值可以用前$k$个部分累加得出，$2^k\sim N$的部分在选上部分$R$之后，剩下的一定比$2^k-1$小，那么再在前$k$个部分中选即可。

代码只展示关键部分，省略头尾的$\text{I/O,new,delete}$等

int v, w, s;
for (int i = 0; i < n; i++) {
    cin >> v >> w >> s;
    for (int p = 1; p <= s; p *= 2) {           //枚举指数增加的部分
        for (int j = m; j >= p * v; j--) {
            dp[j] = max(dp[j], dp[j - p * v] + p * w);
        }
        s -= p;
    }
    if (s > 0) {                                //剩余部分大于0，再多考虑一下剩余部分
        for (int j = m; j >= s * v; j--) {
            dp[j] = max(dp[j], dp[j - s * v] + s * w);
        }
    }
}
cout << dp[m] << endl;

小技巧2的篇幅会比较长，将在多重背包问题2中介绍