闫式dp分析法

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define v first
#define w second

using namespace std;
typedef pair<int,int> PII;
const int N = 70 , M = 32010;
int f[M];
PII master[N];
vector<PII> servent[N];

int n , m;
int main() {
    cin >> m >> n;
    for (int i = 1 ; i <= n ; i ++ ) {
        int v ,w ,q;
        cin >> v >> w >> q;
        if (!q) master[i] = {v ,v * w};
        else servent[q].push_back({v,v * w});
    }


    for (int i = 1 ; i <= n ; i ++ ) {
        for (int j = m ; j >= 0 ; j -- ) {
            if (master[i].v) {
               // int v = master[i].v , w = master[i].w;
                for (int k = 0 ; k < 1 << servent[i].size() ; k ++ ) {
                    int v = master[i].v , w = master[i].w;
                    for (int u = 0 ; u < servent[i].size() ; u ++ ) {
                        if (k >> u & 1) {
                            v += servent[i][u].v;
                            w += servent[i][u].w;
                        }
                    }
                    if (j >= v) f[j] = max(f[j] , f[j - v] + w);
                }

            }
        }
    }

    cout << f[m];
    return 0;
}