思路：首先value数组里每个pair存放的first表示该种组合的体积，second表示该种组合的收益。我采用的预计算的方法先把每个组内的所有可能的方案计算出来存放到value[i]中，然后最后计算最高收益时就相当于是一个分组背包的模版题了。

#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

int w, v, q;
int f[32010];
vector<pair<int, int>> value[60];
int N, M;

int main() {
    cin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        cin >> v >> w >> q;
        if (q == 0) {
            // 当前是元素是主件，直接加入
            value[i].push_back({v, v * w});
        }
        else {
            // 当前元素是附件，生成能和当前附件组合而成的所有可能的选法
            int sz = value[q].size();
            for (int i = 0; i < sz; ++i) {
                value[q].push_back({v + value[q][i].first, value[q][i].second + v * w});
            }
        }
    }

    for (int i = 1; i <= M; ++i) {
        if (value[i].size() == 0) continue;
        for (int j = N; j >= 1; --j) {
            for (int k = 0; k < value[i].size(); ++k) {
                if (j >= value[i][k].first) {
                    f[j] = max(f[j], f[j - value[i][k].first] + value[i][k].second);
                }
            }
        }
    }

    cout << f[N] << endl;
    return 0;
}