【题目来源】
https://www.luogu.com.cn/problem/P1064
https://oj.czos.cn/p/1820
【题目描述】
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 n 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下面就是一些主件与附件的例子：如主件是书柜，附件是图书等。
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、1 个或 2 个附件。每个附件对应一个主件，附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 n 元。于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1~5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 n 元的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 j 件物品的价格为 vj，重要度为 wj，共选中了 k 件物品，编号依次为 j1，j2，…，jk，则所求的总和为：Vj1×Wj1+Vj2×Wj2+·……+ Vjk×Wjk。
请你帮助金明设计一个满足要求的购物单。
【输入格式】
第一行有两个整数，分别表示总钱数 n 和希望购买的物品个数 m。
第 2 到第（m+1）行，每行三个整数，第（i+1）行的整数 vi，pi，qi 分别表示第 i 件物品的价格、重要度以及它对应的的主件。如果 qi=0，表示该物品本身是主件。
【输出格式】
输出一行一个整数表示答案。
【输入样例】
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
【输出样例】
2200
【数据范围】
对于全部的测试点，保证1≤n≤3.2×10^4，1≤m≤60，0≤vi≤10^4，1≤pi≤5，0≤gi≤m，答案不超过 2×10^5。
来源：noip2006 提高组第 2 题。
【算法分析】
● 有依赖的背包（树形背包）核心是物品间存在选子必选父的单向依赖关系，依赖结构通常为森林或多叉树，主流解法为树形 DP 结合分组背包自底向上合并；若题目中是双向强依赖、互相绑定的物品组（选其一必全选），则可先用并查集将连通块缩为超级物品，再套用普通 01 背包求解，两种思路对应不同依赖模型，共同构成完整解法体系。
● 将主件和对应的附件处理成分组，每个主件对应一个组。
（1）如果一个主件有 0 个附件，则该组只有一个物品，对应主件的体积和价值。
（2）如果一个主件有 1 个附件，则该组有两个物品“物品 1：主件的体积和价值，物品 2：主件+附件的体积和价值”。
（3）如果一个主件有 2 个附件，则该组有四个物品“物品 1：主件的体积和价值，物品 2：主件+附件 1 的体积和价值，物品 3：主件+附件 2 的体积和价值，物品 4：主件+物品 1+物品 2 的体积和价值”。
所有分组都有一个体积、价值为 0 的物品，表示不选该分组任何物品。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=65,V=32005;struct Node {int vol;int val;
};
Node zu[N]; //main items
int id[N]; //id of main items
vector<Node> fu[N]; //attachment for the main item
vector<Node> g[N]; //items of the i-th group
int f[V];
int n,m,v,p,q;
int cnt; //number of main componentsint main() {cin>>n>>m;for(int i=1; i<=m; i++) {cin>>v>>p>>q;if(q==0) { //save main itemid[++cnt]=i;zu[i].vol=v;zu[i].val=v*p;} else fu[q].push_back({v,v*p}); //save attachment}for(int i=1; i<=cnt; i++) {int t=id[i];g[t].push_back({0,0});g[t].push_back({zu[t].vol,zu[t].val});if(fu[t].size()>=1) {g[t].push_back({zu[t].vol+fu[t][0].vol,zu[t].val+fu[t][0].val});}if(fu[t].size()>=2) {g[t].push_back({zu[t].vol+fu[t][1].vol,zu[t].val+fu[t][1].val});g[t].push_back({zu[t].vol+fu[t][0].vol+fu[t][1].vol,zu[t].val+fu[t][0].val+fu[t][1].val});}}for(int i=1; i<=cnt; i++) { //group-based knapsackint t=id[i]; //idx of each groupfor(int j=n; j>=0; j--) {for(int k=0; k<g[t].size(); k++) {if(j>=g[t][k].vol) f[j]=max(f[j],f[j-g[t][k].vol]+g[t][k].val);}}}cout<<f[n];return 0;
}/*
in:
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0out:
2200
*/【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/159616887
https://mp.weixin.qq.com/s/_7ag5PRxS4X5R8xAqqYfpQ
https://www.cnblogs.com/hackerchef/p/18150674
https://www.cnblogs.com/zzzsacmblog/p/18715621