这道题可以用分组背包来做。
但是分组有两种方式
一种是把主件,主件+附件1，主件+附件2分成一组
组内只能选一个物品
一种是建一颗树，用树形dp的方式去做
第二种更通用，就算物品的依赖关系是森林都可以做
而第一种只限于这道题，因为只有一层关系，所以有特殊解
目前只写了第一种，后面补第二种
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 412;
const int MAXM = 32123;
int f[MAXM], p[MAXN], w[MAXN], fa[MAXN], n, m;
int W[MAXN], P[MAXN], k[MAXN], cnt, N;void add(int w, int p)
{W[N] = w; P[N] = p; k[N++] = cnt;
}void init()
{REP(i, 1, n + 1)if(fa[i] == 0){add(w[i], p[i]);vector<int> son;REP(j, 1, n + 1)if(fa[j] == i)son.push_back(j);if(son.size() >= 1) add(w[i] + w[son[0]], p[i] + p[son[0]]);if(son.size() >= 2){add(w[i] + w[son[1]], p[i] + p[son[1]]);add(w[i] + w[son[1]] + w[son[0]], p[i] + p[son[1]] + p[son[0]]);}cnt++;}
}int main()
{scanf("%d%d", &m, &n);REP(i, 1, n + 1){scanf("%d%d%d", &w[i], &p[i], &fa[i]);p[i] *= w[i];}init();REP(r, 0, cnt)for(int j = m; j >= 0; j--)REP(i, 0, N)if(k[i] == r && j - W[i] >= 0)f[j] = max(f[j], f[j - W[i]] + P[i]);printf("%d\n", f[m]);return 0;
}第二种
大家有没有看到这个代码和选课的树形dp的区别。（选课https://blog.csdn.net/qq_34416123/article/details/82258060）
这道题是选课的简化版，最多只有两个儿子，而且只有三层。
这份代码多了个递归参数体积。选课那题体积都为1，而cnt数组记录的是以i结尾的子树
的节点的个数，也就是体积。
#include<cstdio>
#include<algorithm>
#include<vector>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 112;
const int MAXM = 32123;
int f[MAXN][MAXM], p[MAXN], w[MAXN], n, m;
vector<int> g[MAXN];void dfs(int u, int k)
{REP(i, 0, g[u].size()){int v = g[u][i];FOR(j, 0, k - w[v]) f[v][j] = f[u][j];if(k >= w[v]) dfs(v, k - w[v]);FOR(j, w[v], k) f[u][j] = max(f[u][j], f[v][j-w[v]] + w[v] * p[v]);}
}int main()
{scanf("%d%d", &m, &n);FOR(i, 1, n){int fa;scanf("%d%d%d", &w[i], &p[i], &fa);g[fa].push_back(i);}dfs(0, m);printf("%d\n", f[0][m]);return 0;
}