依赖背包
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
#include <iomanip>
const int N = 32000 + 10;
const int INF = 0x3f3f3f3f;
using namespace std;

struct node{
	int w , v , w1 ,v1 , w2 , v2;
}a[70];

int m , n , dp[N] ,x , y , z;

int main()
{
	cin >> m >> n;
	for(int i = 1 ; i <= n; i++)
	{
		cin >> x >> y >> z;//x是价格  y重要度  z主件
		if( !z )//主件 
		{
			a[i].w = x;
			a[i].v = x * y; 
		} 
		else//附件 
		{
			if(a[z].v1)
			{
				a[z].w2 = x;
				a[z].v2 = x * y;
			}
			else
			{
				a[z].w1 = x;
				a[z].v1 = x * y;
			}
		}
	}

	for(int i = 1 ; i <= n; i++)
	{
		if(!a[i].v)	continue;
		for(int j = m; j >= a[i].w; j--)
		{
			//考虑  不买 ，买主件 
			dp[j] = max(dp[j] , dp[j - a[i].w] + a[i].v);
			if(j >= a[i].w + a[i].w1)//买主 + 附1 
				dp[j] = max(dp[j] , dp[j - a[i].w - a[i].w1] + a[i].v + a[i].v1); 
			if(j >= a[i].w + a[i].w2)//买主 + 附2 
				dp[j] = max(dp[j] , dp[j - a[i].w - a[i].w2] + a[i].v + a[i].v2);
				
			if(j >= a[i].w + a[i].w1 + a[i].w2)//买主 + 附1  + 附2 
				dp[j] = max(dp[j] , dp[j - a[i].w - a[i].w1 - a[i].w2] + a[i].v + a[i].v1 + a[i].v2);
		 }
	}
	cout << dp[m];
	return 0;
}

借鉴了张老师的代码