参考代码

#include <bits/stdc++.h>
using namespace std;
int V, n, T;
int f[70][40000], w[70][40000], c[70][40000], cnt[70];
int _w, _c, t;
int v[70], p[70], q[70];
int main() {
    cin >> V >> n;
    T = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i] >> p[i] >> q[i];
    }
    for (int i = 1; i <= n; ++i)
        if (q[i] == 0) {
            T++;
            cnt[T]++;
            w[T][cnt[T]] = v[i];
            c[T][cnt[T]] = v[i] * p[i];
            int f1 = -1, f2 = -1;
            for (int j = 1; j <= n; ++j)
                if (q[j] == i) {
                    if (f1 == -1)
                        f1 = j;
                    else
                        f2 = j;
                }
            if (f1 != -1) {
                cnt[T]++;
                w[T][cnt[T]] = v[i] + v[f1];
                c[T][cnt[T]] = v[i] * p[i] + v[f1] * p[f1];
            }
            if (f2 != -1) {
                cnt[T]++;
                w[T][cnt[T]] = v[i] + v[f2];
                c[T][cnt[T]] = v[i] * p[i] + v[f2] * p[f2];

                cnt[T]++;
                w[T][cnt[T]] = v[i] + v[f1] + v[f2];
                c[T][cnt[T]] = v[i] * p[i] + v[f1] * p[f1] + v[f2] * p[f2];
            }
        }
    for (int i = 1; i <= T; ++i)
        for (int j = 0; j <= V; ++j) {
            f[i][j] = f[i - 1][j];
            for (int k = 1; k <= cnt[i]; ++k)
                if (j >= w[i][k])
                    f[i][j] = max(f[i][j], f[i - 1][j - w[i][k]] + c[i][k]);
        }
    cout << f[T][V];
    return 0;
}