分组背包问题
分组背包问题是背包问题的又一个变种。
问题描述
将所有物品分为若干组，每组中的物品存在依赖或排斥关系（通常每组只能选一个物品）。
解决思路
将每组看作一个整体，遍历每组中的每个物品，化归为 0-1 背包问题进行求解。
对于每组物品，枚举组内的每个物品，将其作为当前组的选择，取价值最大的方案。
状态转移
对于每组，可以选择不选该组任何物品，或者从该组中选择一个物品放入背包，取所有方案中价值最大的。
链接到
- 上一个知识点：2.6 完全背包问题
- 下一个知识点：无（本章最后一个知识点）