lanqiao OJ 金明的预算方案

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define v first 
#define w second 
 
using namespace std ; 
const int N = 2e5 +10 ;
int f[N] ;
typedef pair<int,int> PII ;
PII master[N] ;//用于记录主件，如果主件的v等于零，说明这个编号的零件不是主件 
vector<PII> s[N] ;//用于记录附件，对于编号为i的主件的附件 
int n , m ;
int main(){
  cin >> m >> n ;
  for(int i = 1 ; i <= n ;i ++){
    int a , b , c ;
    cin >> a >> b >> c ;
    if(c==0){
      master[i] = {a,a*b} ;//加入主键 
    }else {
      s[c].push_back({a,a*b}) ;//加入附件 
    }
  }
  for(int i = 1 ; i <= n ;i ++){
    if(master[i].v == 0) continue ;//如果不是主件，就直接continue； 
    else{
      for(int j = m ; j >= 0 ; j --){
        PII tmp = master[i];
        for(int k = 0 ; k < 1 << s[i].size() ; k++){
          int  v = tmp.v ; int w = tmp.w ;//如果要选附件，主件必须选 
          for(int u = 0 ; u <= s[i].size() ; u ++  ){//利用二进制的方法来求附件的选择和不选择 
            if((k>>u)&1){
              v += s[i][u].v ;
              w += s[i][u].w ;
            }
          }
          if(j >= v ) f[j] = max(f[j],f[j-v] + w) ;
        }
      }
      
      
    }
  }
  cout << f[m] << endl ;
}