问题模型：这是一个有依赖的背包问题（分组背包）。每个主件可以有0、1或2个附件，附件依赖于主件（即购买附件必须先购买其主件）。由于附件数量最多为2，我们可以将每个主件及其附件的所有合法购买组合看作一个物品组，组内物品互斥（只能选择一种组合），然后使用分组背包动态规划求解。
数据范围反推算法复杂度：
- 总钱数 $n \le 3.2 \times 10^4$，物品个数 $m \le 60$。
- 每个主件最多有2个附件，因此每个主件组最多有4种购买方案（主件、主件+附件1、主件+附件2、主件+附件1+附件2）。
- 分组背包的复杂度为 $O(n \times \text{总方案数})$，总方案数最多 $4m = 240$，因此最坏操作次数约为 $3.2 \times 10^4 \times 240 = 7.68 \times 10^6$，在 C++ 中完全可行。
- 作为专业选手，必须准确识别依赖背包并转化为分组背包模型。 新手常犯的错误是试图用搜索枚举所有组合或直接套用 0-1 背包，导致超时或结果错误。
状态定义：
设 $\text{dp}[j]$ 表示花费不超过 $j$ 元所能获得的最大价值（价格与重要度乘积之和）。
状态转移（分组背包标准转移）：
对于每个主件组（设该组有 $s$ 种购买方案），每种方案有一个价格 $\text{price}$ 和价值 $\text{value}$。我们要求每组最多选择一种方案，因此采用类似 0-1 背包的倒序更新，但需要在容量循环内部枚举组内所有方案：
$$
\text{dp}[j] = \max(\text{dp}[j], \ \text{dp}[j - \text{price}_k] + \text{value}_k) \quad (\text{对于组内每种方案 } k)
$$
关键步骤：
1. 预处理分组：遍历所有物品，将附件关联到对应的主件。对于每个主件，生成所有合法的购买方案：
- 只买主件。
- 买主件 + 附件1（如果存在）。
- 买主件 + 附件2（如果存在）。
- 买主件 + 附件1 + 附件2（如果存在）。
计算每种方案的总价格和总价值（价格 × 重要度之和）。
2. 分组背包 DP：依次处理每个主件组，对容量 $j$ 从 $n$ 到 $0$ 倒序循环（保证每组只选一种方案），然后枚举该组的所有方案进行状态转移。
初始化：
- $\text{dp}[0] = 0$，其他 $\text{dp}[j] = 0$。
最终答案：$\text{dp}[n]$。
图解辅助（以样例为例）：
输入：
n=1000, m=5
物品：
1: v=800, p=2, q=0 (主件)
2: v=400, p=5, q=1 (附件，属于主件1)
3: v=300, p=5, q=1 (附件，属于主件1)
4: v=400, p=3, q=0 (主件)
5: v=500, p=2, q=0 (主件)
主件1的购买方案：
1. 只主件： price=800, value=800*2=1600
2. 主件+附件2： price=800+400=1200, value=1600+400*5=3600
3. 主件+附件3： price=800+300=1100, value=1600+300*5=3100
4. 主件+附件2+附件3： price=800+400+300=1500, value=1600+2000+1500=5100
主件4的方案：只主件： price=400, value=400*3=1200
主件5的方案：只主件： price=500, value=500*2=1000
分组背包DP过程（简化）：
初始dp全0。
处理主件1组：更新后，dp[800]=1600, dp[1200]=3600（但n=1000，所以1200和以上不会影响最终结果）
处理主件4组：更新后，dp[400]=1200, dp[800]=max(1600, dp[400]+1200)=max(1600, 1200+1200=2400)=2400?
注意：dp[400]在处理主件4组时还是0（因为倒序更新，dp[400]尚未被当前组更新），所以dp[800]仍为1600。
实际上，更准确地说，处理主件4组时，对于j=800，dp[800] = max(1600, dp[400]+1200)=max(1600, 0+1200)=1600。
之后dp[900] = max(0, dp[500]+1200)，其中dp[500]可能为0。
处理主件5组：更新后，dp[500]=1000, dp[900]=max(dp[900], dp[400]+1000)=max(1200, 1200+1000=2200)=2200。
最终dp[1000]可能是2200（由dp[500]+主件5? 但dp[500]=1000，加上主件5得2000；或者dp[400]+主件5? dp[400]=1200，加上主件5得2200）。
所以最优方案为主件4+主件5，总价900，价值2200。
#include <bits/stdc++.h>
using namespace std;
struct Option {
int price; // 方案总价格
int value; // 方案总价值（价格*重要度之和）
};
int main() {
// IO加速
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> v(m + 1), p(m + 1), q(m + 1);
vector<vector<int>> attachments(m + 1); // attachments[主件编号]存储附件编号
// 读入数据，建立主件与附件的关系
for (int i = 1; i <= m; ++i) {
cin >> v[i] >> p[i] >> q[i];
if (q[i] != 0) {
attachments[q[i]].push_back(i);
}
}
// dp[j]: 花费不超过j元的最大价值
vector<int> dp(n + 1, 0);
// 遍历每个物品，只处理主件（q[i]==0）
for (int i = 1; i <= m; ++i) {
if (q[i] != 0) continue; // 跳过附件
// 生成当前主件的所有购买方案
vector<Option> options;
// 方案1: 只买主件
options.push_back({v[i], v[i] * p[i]});
int num_att = attachments[i].size();
// 处理附件组合
if (num_att >= 1) {
int att1 = attachments[i][0];
// 方案2: 主件 + 附件1
options.push_back({v[i] + v[att1],
v[i] * p[i] + v[att1] * p[att1]});
if (num_att >= 2) {
int att2 = attachments[i][1];
// 方案3: 主件 + 附件2
options.push_back({v[i] + v[att2],
v[i] * p[i] + v[att2] * p[att2]});
// 方案4: 主件 + 两个附件
options.push_back({v[i] + v[att1] + v[att2],
v[i] * p[i] + v[att1] * p[att1] + v[att2] * p[att2]});
}
}
// 分组背包更新：对每个组，容量倒序，枚举组内所有方案
for (int j = n; j >= 0; --j) {
for (const Option& opt : options) {
if (j >= opt.price) {
dp[j] = max(dp[j], dp[j - opt.price] + opt.value);
}
}
}
}
cout << dp[n] << '\n';
return 0;
}
代码风格说明：
- 使用
vector 存储数据和 dp 数组，自动管理内存。
- 使用
Option 结构体清晰表示每种购买方案。
- 关键点：分组背包的更新顺序——容量倒序，组内方案枚举在容量循环内部，确保每组最多选一种方案。
- 输入输出加速，提高程序效率。
鲁棒性处理：
- 附件列表可能为空，因此需要判断
num_att 的大小。
- 方案价格可能超过当前容量
j，因此需要判断 j >= opt.price。
- 初始化 dp 为 0，符合 0 元花费价值为 0 的实际情况。
- 由于价格和重要度乘积可能较大，但题目保证答案不超过 $2 \times 10^5$，使用
int 足够。
时间复杂度：$O(n \times s)$，其中 $s$ 是总方案数，最多 $4m = 240$。因此最坏约 $3.2 \times 10^4 \times 240 = 7.68 \times 10^6$ 次操作，完全可行。
空间复杂度：$O(n + m)$，存储 dp 数组和物品信息。
进一步优化：
- 如果 $n$ 很大（比如 $10^5$ 以上），但 $m$ 很小，可以考虑其他优化，但本题不需要。
- 由于价格是 10 的整数倍，可以除以 10 缩小规模，但 dp 数组大小也会缩小，不过实现复杂度增加，且本题数据范围已可接受。
总结：本题是分组背包的经典例题，关键在于将依赖关系转化为物品组。作为专业选手，必须掌握：
- 识别依赖背包并转化为分组背包模型的能力。
- 生成所有合法购买方案的方法（枚举子集）。
- 分组背包的标准实现（容量倒序，组内方案枚举在内层）。
常见错误提醒：
- 错误地允许附件单独购买，没有与主件绑定。
- 分组背包更新顺序错误（如先枚举方案再枚举容量，会导致同一组内物品被多次选择）。
- 忘记附件可能为 0 个或 1 个的情况，导致数组越界。
现在，请自己实现代码，并尝试思考：如果附件也有自己的附件（形成树形依赖），该如何解决？这是更复杂的树形依赖背包问题，有助于拓展思维。