P1757 通天之分组背包

#include<bits/stdc++.h>
#define N 1001
using namespace std;
struct Object{
	int a,b,c;
}ob[N]; 
long long n,m;
bool b[101];
map<int,int> p;
long long maxprice(int num,bool bo[],map<int,int> mp){
	if(num>n){
		long long weight=0,price=0;
		for(int i=1;i<=1000;i++){
			if(bo[i]){
				weight+=ob[mp[i]].a;
				price+=ob[mp[i]].b;
			}
		}
		if(weight>m)return 0;
		return price;
	}
	long long a=0,b=0;
	a=maxprice(num+1,bo,mp);
	bo[ob[num].c]=1;
	mp[ob[num].c]=num;
	b=maxprice(num+1,bo,mp);
	return max(a,b);
}
signed main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>ob[i].a>>ob[i].b>>ob[i].c;
	}
	cout<<maxprice(1,b,p);
	return 0;
}