思路描述

提升速度的主要思路是认识到对一个相同的 i （主件），所进行的分组也是相同的，因此在循环体积（预算 / m）前，先把所有的分组预处理出来，保存到辅助数组aux中，就可以当作正常的分组背包问题做了。预计会快大约一倍。

#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 60, M = 32000;

int n, m;
PII master[N];
vector<PII> servant[N];
int f[M];
PII aux[4];

int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; ++i)
    {
        int v, p, q;
        scanf("%d%d%d", &v, &p, &q);
        if (q == 0) master[i] = { v, v * p };
        else servant[q].push_back({ v, v * p });
    }

    for (int i = 1; i <= n; ++i)
    {
        if (!master[i].first && !master[i].second) continue;

        // 分组
        for (int j = 0; j < 1 << servant[i].size(); ++j)
        {
            int v = master[i].first, w = master[i].second;
            for (int k = 0; k < servant[i].size(); ++k)
                if (j >> k & 1)
                {
                    v += servant[i][k].first;
                    w += servant[i][k].second;
                }
            aux[j] = { v, w };
        }

        // dp
        for (int j = m; j >= 0; --j)
            for (int k = 0; k < 1 << servant[i].size(); ++k)
                if (j >= aux[k].first)
                    f[j] = max(f[j], f[j - aux[k].first] + aux[k].second);
    }

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