C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 70, M = 32010;

typedef pair<int, int> PII;

PII master[N];//主件
vector<PII> servent[N];//从件
int dp[M];
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)//从件
            servent[q].push_back({v, v*w});
        else//主件
            master[i] = {v, v*w};        
    }

    for(int i = 1;i <= n;++i)//枚举每一组
        for(int j = m;j >= 0;--j)//枚举容量
            for(int k = 0;k < 1 << servent[i].size();++k){//枚举每一种附件的选取方案
                int v = master[i].first, w = master[i].second;//主件
                for(int t = 0;t < servent[i].size();++t)
                    if(k >> t & 1){
                        v += servent[i][t].first;
                        w += servent[i][t].second;
                    }
                if(j >= v) 
                    dp[j] = max(dp[j], dp[j-v]+w);
            }

    cout << dp[m];       
}