多重背包

朴素的多重背包没什么好讲的。不过由于复杂度过高(O(vnm))很容易被卡，下面讲两种优化。

说明：除代码外所有的重量/体积用v表示，价值用w表示，个数用m表示

代码以洛谷 P1776【宝物筛选_NOI导刊2010提高（02）】为例

第一种优化：二进制拆分

我们将m按照2^0，2^1，2^2……，最后将剩下的那个单独分一组，然后就可以将个数减小到logn的级别，复杂度O(vnlogm)。

#include <iostream>
#include <cstdio>
using namespace std;
int n, ww, f[40005];
int main()
{
    cin >> n >> ww;
    for (int i = 1; i <= n; ++i)
    {
        int v, w, m, cnt = 0, c[100];
        cin >> v >> w >> m;
        for (int j = 1; j <= m; j *= 2)
        {
            m -= j;
            c[++cnt] = j;
        }
        if (m)
            c[++cnt] = m;
        for (int j = 1; j <= cnt; ++j)
            for (int k = ww; k >= w * c[j]; --k)
                f[k] = max(f[k], f[k - w * c[j]] + v * c[j]);
    }
    printf("%d", f[ww]);
    return 0;
}

第二种优化：单调队列优化

我们可以发现，每加入一个物品的时候，对于每个f值的转移，我们可以按照%w的余数进行分组，因为显然对于这个物品造成的影响，它只能用%w同余的f的值进行转移。

进行分组之后，我们可以发现：对于每个f[j+l*w]（其中w表示余数，l为使得j+l*w小于等于背包重量的任意非负整数），它可以由f[j+k*w]转移（其中k为小于等于l的非负整数且l-k<=m），转移方程为f[j+l*w]=f[j+k*w]+(l-k)*v，然后就可以发现f[j+l*w]=(f[j+k*w]-k*v)+l*v，对于f[j+k*w]-k*v单调队列转移一波就可以了。复杂度成功降为O(vn);

PS：注意特判一下w等于0的情况。

#include <iostream>
#include <cstdio>
using namespace std;
int n, ww, ans, f[40005], q[40005], s[40005];
int main()
{
    scanf("%d%d", &n, &ww);
    for (int i = 1; i <= n; ++i)
    {
        int v, w, m;
        scanf("%d%d%d", &v, &w, &m);
        if (!w)
        {
            ans += v * m;
            continue;
        }
        int k = ww / w;
        for (int j = 0; j < w; ++j)
        {
            int head = 1, tail = 0;
            for (int l = 0; l <= k; ++l)
            {
                int num = f[j + l * w] - l * v;
                while (head <= tail && q[tail] < num)
                    --tail;
                q[++tail] = num;
                s[tail] = l;
                while (head <= tail && l - s[head] > m)
                    ++head;
                f[j + l * w] = max(f[j + l * w], q[head] + l * v);
            }
        }
    }
    printf("%d", ans + f[ww]);
    return 0;
}