分组选择
每组至多选一个带权元素,按权值降序加入;是贪心选择模型的最小入门题,也是划分拟阵的实例。标签 贪心 / 选择 / 分组 / 拟阵
题目描述
有 个组和 个元素。第 个元素属于第 组,权值为 。
选择一个元素集合 ,使每个组中至多有一个元素被选中,并最大化
,,。
题解
本题对应贪心选择模型:
- :所有元素;
- :每个组至多选一个元素的集合族;
- ,故 ;
- 的非减序就是 的非增序;
- 极大可行集:每个非空组各选一个元素;
- 最优解:使 最小,即权和最大。
把所有元素按权值从大到小排序。维护每个组是否已经选过元素。
依次扫描元素 :
- 若第 组已经选过元素,跳过;
- 否则选中 ,并把第 组标记为已选。
正确性用交换论证。设当前贪心集合为 ,并假设存在最优解 满足 。处理元素 时:
- 若 已被 使用,则 中也有同组元素,不能再选 ,跳过安全。
若 未被 使用:
- 若 ,不变量保持;
- 若 ,且 中有同组元素 ,则用 替换 。由于按权值降序处理,,替换后仍可行且总权值不降;
- 若 中没有同组元素,则加入 不破坏可行性且总权值增大,矛盾。
因此每一步都保持“存在最优解包含当前贪心集合”,最终贪心集合就是最优解。
该可行集族就是划分拟阵的独立集族,因此这也为拟阵页提供了一个直接实例。
复杂度
排序为 ,扫描为 ,空间为 。