背包dp题解（洛谷搬运md重做）

思路

我看到题的第一反应是按照主件进行分组，组内进行 01 背包。但是，这只是一道 绿题(编者注:此题在洛谷是一道普及+/提高−的绿题)啊，不可能这么麻烦。注意到题目中说
每个主件可以有0 个、1 个或 2 个附件。

所以对于每组只有 5 种情况：

1.什么都不买
2.只买主件
3.买主件和第一个附件（前提是有第一个附件）
4.买主件和第二个附件（前提是有第二个附件）
5.买主件和两个附件（前提是有两个附件）
然后对以上方案产生的价值取最大值。

状态转移方程和基础的背包一样，这里不再赘述。

代码实现

可以建一个结构体，里面包含 v,p,q,lc,rc，分别表示物品的价格、重要度以及它对应的的主件、第一个附件、第二个附件。边读入边处理，如果这件物品是附件，找到它的主件，并判断是第几个主件。