@[xixi_bang](/user/322896)
本题可以归结为背包问题。背包问题有四种基本类型，分列如下（参见我写的书 [《C++，挑战编程——程序设计竞赛进阶训练指南》](https://blog.csdn.net/metaphysis/article/details/90288252) 第 11 章“动态规划”第 11.1 节“背包问题”的内容）：
基本背包问题：
给定一个容量为 $C$ 的背包，现有 $n$ 个物品，每个物品具有容量 $C_i$ 和价值 $P_i$，$1≤i≤n$，问如何选取放入背包的物品，使得背包内的物品容量之和不超过 $C$ 且价值之和最大。由于物品要么放入背包，要么不放入背包，设xi表示物品在背包中的状态，则有 $x_i$ ∈ {0，1}，故称01背包问题。
完全背包问题：
给定一个容量为 $C$ 的背包，有 $n$ 种物品，每种物品都有容量 $C_i$ 和价值 $P_i$，$1≤i≤n$，假设每种物品的数量不限，问如何选取放入背包的物品，使得背包内的物品容量之和不超过 $C$ 且价值之和最大。
多重背包问题：
给定一个容量为 $C$ 的背包，有 $n$ 种物品，每种物品都有容量 $C_i$ 和价值 $P_i$，且有数量上限 $Q_i$，$1≤i≤n$，问如何选取放入背包的物品，使得背包内的物品容量之和不超过 $C$ 且价值之和最大。
部分背包问题：
给定一个容量为 $C$ 的背包，有 $n$ 个物品，每个物品都有容量 $C_i$ 和价值 $P_i$，$1≤i≤n$，物品可以拆分且可取全部或一部分放入背包，问如何选取放入背包的物品，使得背包内的物品容量之和不超过 $C$ 且价值之和最大。
前三种背包问题可以使用动态规划解决，最后一种部分背包问题可以通过贪心算法解决。
从题目的约束来看，属于基本背包问题的一种变形。预算 $N$ 等价于背包的容量，$m$ 为物品的个数，物品的价格 $v$ 等价于物品的容量 $C_i$，物品的价值为物品的价格 $v$ 和重要度 $p$ 的乘积。与基本的背包问题稍有差异的地方是：题目限制了必须购买主件才能购买附件。那么可以令法 $f[i]$ 表示预算为不超过 $i$ 时能够得到的价格与重要度乘积的总和的最大值，那么我么可以按照解决基本背包问题的思路，从第一件物品枚举到第 $m$ 件物品，检查放入某种物品是否可能更新最优值。由于限制了必须购买主件才能购买附件，对于第 $j$ 种主件来说，可以令 $h[i]$ 表示在前 $j-1$ 中主件和附件可选的情况下，预算不超过 $i$ 时能够得到的最优值，然后考虑购买第 $j$ 种主件和其附件是否能够更新最优值。
以上是解题思路的概述，如果您大致理解了，可以继续参考以下的代码注释进行理解。
```
// 读入 m 种物品的价格、重要度，第 i 种物品的价值为其价格和重要度的乘积。
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &a[i].v, &a[i].p, &a[i].q);
a[i].p *= a[i].v;
}
// 逐个物品考虑是否放入背包。
for(int i = 1; i <= m; i++)
// 题目的特殊限制：必须先放主件。当 a[i].q 为 0 时表示主件。
if(!a[i].q)
{
// 初始化 h 数组，因为第 i 种物品的价格为 a[i].v，
// 所以当预算小于 a[i].v 时，能够得到的最大价值为 0。
for(int j = 1; j < a[i].v; j++) h[j] = 0;
// 考虑购买该种主件，在原有的最优值数组 f 上更新得到最优值数组 h。
for(int j = a[i].v; j <= n; j++) h[j] = f[j - a[i].v] + a[i].p;
// 考虑购买主件的附件。
for(int j = 1; j <= m; j++)
// 检查当前物品是否为主件 i 的附件。
if(a[j].q == i)
// 检查放入附件 j 是否能够更新最优值。注意容量 k 的枚举顺序和下限值。
// k 从大到小枚举可以节省动态规划状态数组的一维存储空间。
// 参见我写的书 [《C++，挑战编程——程序设计竞赛进阶训练指南》]
// 第 11 章“动态规划”第 11.9 节“动态规划的优化”第
// 11.9.1 小节“空间优化”的内容。
for(int k = n; k >= a[i].v + a[j].v; k--)
h[k] = max(h[k], h[k - a[j].v] + a[j].p);
// 数组 h 存储的是考虑放入第 i 种主件及其附件后的最优值，
// 数组 f 存储的是不考虑放入第 i 种主件及其附件的最优值，
// 取两者的较优值。由于必须放入主件，故从 a[i].v 开始考虑更新。
for(int j = a[i].v; j<=n; j++) f[j] = max(f[j], h[j]);
}
// 输出最优值。
printf("%d\n",f[n]);
```
如果您有其他问题，欢迎您@我，如果时间允许的话，我很乐意提供帮助。
by metaphysis @ 2020-04-05 19:57:54
@[metaphysis](/user/333388) 明白了！谢谢您这么耐心的解答！您实在很细心且逻辑清晰！之后有问题还烦请您指导！
by xixi_bang @ 2020-04-05 20:37:23