算法分析$O(nm)$

将组件和附件看成一组物品，枚举每个物品和当前这组物品的附属选择.

【代码实现】

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define v first
#define w second
const int N=75,M=32010;
int f[M];
PII master[N]; //主件
vector<PII> g[N]; //附件
int main()
{
	int V,n;
	cin>>V>>n;
	for(int i=1;i<=n;i++)
	{
		int v,w,q;
		cin>>v>>w>>q;
		if(!q) //主件
		{
			master[i]={v,v*w};
		}
		else //加入到对应的附件之中
		{
			g[q].push_back({v,w*v});
		}
	}
	for(int i=1;i<=n;i++) //枚举第i组物品
	{
		for(int j=V;j>=0;j--) //枚举第i组物品
		{
			for(int u=0;u<1<<g[i].size();u++) //如果当前物品是附件,这里不会执行
			{
				int v=master[i].v,w=master[i].w; //加上当前主件
				for(int k=0;k<g[i].size();k++) //枚举组件的附属品
				{
					if(u>>k&1)
					{
						v+=g[i][k].v;
						w+=g[i][k].w;
					}
				}
				if(j>=v) //可以更新
				{
					f[j]=max(f[j],f[j-v]+w);
				}
			}
		}
	}
	cout<<f[V];
	return 0;
}