不妨看看我花了一小时脑子一抽写的离谱代码：

// Problem: P1064 [NOIP2006 提高组] 金明的预算方案
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1064
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
#define MA 1000010

int n,m,u[MA],p[MA],cnt,c,dp[MA];
int uu[MA],pp[MA];

vector<int> v[MA]; //第i个有哪些附属
vector<int> mas;	//不是附属的有哪些

int f[1000][1000];//分组背包，第i组有哪些下标
int b[MA]; //第i组有几个物品

int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1;i<=m;i++){
		int k;
		scanf("%d%d%d",&u[i],&p[i],&k);
		if(k!=0)v[k].push_back(i);//第k个的附属加上这个
		else mas.push_back(i);//不是附属的加一个
	}
	for(int i = 0;i<mas.size();i++){
		//mas[i]为当前不是附属的
		int mu = u[mas[i]],mp = p[mas[i]];
		if(v[mas[i]].size()==0){
			//一个服书也没有
			uu[++cnt] = mu;
			pp[cnt] = mp*mu;
			
			c++; //c为组下标
			b[c] = 1; //第c组数量
			f[c][b[c]] = cnt;
		}
		else if(v[mas[i]].size()==1){
			//一个附属
			uu[++cnt] = mu;
			pp[cnt] = mp*mu;
			
			c++; //c为组下标
			b[c] = 1; //第c组数量
			f[c][b[c]] = cnt;
			
			int v1 = v[mas[i]][0];//第一个附属的下标
			uu[++cnt] = mu+u[v1];
			pp[cnt] = mp*mu+p[v1]*u[v1];
			//c++; //c为组下标
			b[c] = 2; //第c组数量
			f[c][b[c]] = cnt;
		}
		else if(v[mas[i]].size()==2){
			//两个附属
			uu[++cnt] = mu;
			pp[cnt] = mp*mu;
			
			c++; //c为组下标
			b[c] = 1; //第c组数量
			f[c][b[c]] = cnt;
			
			int v1 = v[mas[i]][0];//第一个附属的下标
			uu[++cnt] = mu+u[v1];
			pp[cnt] = mp*mu+p[v1]*u[v1];
			
			//c++; //c为组下标
			b[c] = 2; //第c组数量
			f[c][b[c]] = cnt;
			
			int v2 = v[mas[i]][1]; //第二个附属的下标（反正最多两个）
			uu[++cnt] = mu+u[v2];
			pp[cnt] = mp*mu+p[v2]*u[v2];
			
			//c++; //c为组下标
			b[c] = 3; //第c组数量
			f[c][b[c]] = cnt;
			
			uu[++cnt] = mu+u[v1]+u[v2];
			pp[cnt] = mp*mu+p[v1]*u[v1]+p[v2]*u[v2];
			
			//c++; //c为组下标
			b[c]=4; //第c组数量
			f[c][b[c]] = cnt;
		}
	}
	/*
	for(int i = 1;i<=c;i++){
		for(int j = 1;j<=b[i];j++){
			printf("%d %d %d\n",f[i][j],uu[f[i][j]],pp[f[i][j]]);
		}
		printf("----------\n");
	}*/
	for(int i = 1;i<=c;i++){
		for(int j = n;j>=0;j--){
			for(int k = 1;k<=b[i];k++){
				int now = f[i][k];
				//printf("%d %d %d\n",now,uu[now],pp[now]);
				
				if(j>=uu[now]){
					//printf(":%d %d --> ",dp[j],dp[j-uu[now]]+pp[now]);
					dp[j] = max(dp[j],dp[j-uu[now]]+pp[now]);
					//printf("%d\n",dp[j]);
				}
				
			}
		}
	}
	printf("%d",dp[n]);
	return 0;
}

分组过程不知道能不能再优化一下，太恶心了