P1782 旅行商的背包

P1782 旅行商的背包

简单的多重背包问题。二进制拆分会比单调队列快。另外，注意第二部分 $m$ 个物品的枚举顺序。如果先枚举个数，再枚举体积会允许一个物品的体积算为两种，导致答案不正确。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
int n, m, V, f[N];
int main()
{
    scanf("%d%d%d", &n, &m, &V);
    for (int v, w, s; n; n--)
    {
        scanf("%d%d%d", &v, &w, &s);
        for (int k = 1; k <= s; s -= k, k <<= 1)
            for (int j = V; j >= v * k; j--)
                f[j] = max(f[j], f[j - v * k] + w * k);
        for (int j = V; j >= v * s; j--)
            f[j] = max(f[j], f[j - v * s] + w * s);
    }
    for (int a, b, c; m; m--)
    {
        scanf("%d%d%d", &a, &b, &c);
        for (int j = V; j >= 0; j--)
            for (int k = 0; k <= j; k++)
                f[j] = max(f[j], f[j - k] + a * k * k + b * k + c);
    }
    printf("%d", f[V]);
    return 0;
}