题解 | 购物单

#include<bits/stdc++.h>
using namespace std;
int main(){

   // 输入，准备容器
   int n,m;
   cin >> n>>m;
   vector<int> v(m+1), w(m+1),q(m+1);
   vector<vector<int>> attachments(m+1);
    vector <int> dp(n+1,0);
   for(int i = 1;i<=m;i++){
    cin >> v[i] >> w[i] >> q[i];
    if(q[i] > 0){
        attachments[q[i]].push_back(i);
    }
   }
   // 创造组合
   for(int i = 1;i<=m;i++){
     if(q[i] == 0){
        vector<pair<int,int>> combinations;
        vector <int> att = attachments[i];
        int count = att.size();
        combinations.push_back({v[i],v[i]*w[i]});
        if(count >= 1){
            int a1 = att[0];
            combinations.push_back({v[i] + v[a1],v[i] * w[i] + v[a1]*w[a1]});
        }
        if(count >= 2){
            int a2= att[1];
            combinations.push_back({v[i] + v[a2],v[i]*w[i]+v[a2]*w[a2]});
        }
        if(count >= 2){
            int a1 = att[0];
            int a2 = att[1];
            combinations.push_back({v[i] + v[a1] + v[a2] , v[i]*w[i]+ v[a1]*w[a1] + v[a2]*w[a2]});
        }
       
        for(int j = n;j>=0;j--){
            for(auto & comb:combinations){
                int cost = comb.first;
                int value = comb.second;
                if(j>=cost){
                    dp[j] = max(dp[j],dp[j-cost]+ value);
                }
            }
        }
     }
   }
   cout << dp[n]<< endl;
   return 0;
}