限制:每个物品有$S_i$个

$1.$ 多重背包问题 I 暴力 $O(NVS)$

for (int i = 1; i <= n; i ++)
    for (int j = 0; j <= m; j ++) // 这里因为没有优化第一维，所以两种枚举顺序都可
        for (int k = 0; k <= s[i] && k * v[i] <= j ; k ++) // k表示个数
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);

$2.$ 多重背包问题 II 二进制打包优化(转化为$01$背包) $O(NVlog_2S)$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25000, M = 2010;

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

int main()
{
    scanf("%d %d", &n, &m);

    int cnt = 0;
    for (int i = 1; i <= n; i ++)
    {
        int a, b, c;
        scanf ("%d %d %d", &a, &b, &c);

        int k = 1;
        while (k <= c)
        {
            cnt ++; // 这是一个包装好的物品
            v[cnt] = a * k;
            w[cnt] = b * k;
            c -= k;
            k <<= 1;
        }

        if (c) // 如果还有剩余，那么剩下的物品包装成一个物品
        {
            cnt ++;
            v[cnt] = a * c;
            w[cnt] = b * c;
        }
    }
    // 再做一遍01背包
    n = cnt;
    for (int i = 1; i <= n; i ++)
        for (int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    printf ("%d", f[m]);
    return 0;
}

$3.$ 多重背包问题 III单调队列优化 $O(NV)$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 20020;

int n, V;
int f[N], g[N], q[N];

int main()
{
    cin >> n >> V;

    for (int i = 1; i <= n; i ++)
    {
        int v, w, s;
        cin >> v >> w >> s;

        memcpy(g, f, sizeof f);
        for (int j = 0; j < v; j ++)
        {
            int hh = 0, tt = -1;
            for (int k = j; k <= V; k += v)
            {
                if (hh <= tt && q[hh] < k - s * v) hh ++;
                // 先判断一下队头元素是不是已经滑出了窗口
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt --;
                // 比当前这个元素小且在这个元素之前的元素对后面的元素贡献值为0,可以之间弹出队列
                q[++ tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
                // 队头维护的是窗口最大值
            }
        }
    }
    // 最后的答案是f[]
    cout << f[V];
    return 0;
}