贪心算法专题-课时2
贪心算法专题课时2:分组选择、贪心选择模型、拟阵与拟阵基定理、拟阵实例,以及单位时间任务调度。
-
单独打开
每组至多选一个带权元素,按权值降序,能选就选。
- 可行集族对子集封闭,是选择模型的直接实例。
- 用交换论证证明跳过和加入都是安全的;后续可用划分拟阵解释。
-
单独打开
按元素代价非减处理,能加入当前可行集就加入。
- 可行族对子集封闭时,维护已选集合与安全加入条件。
- 拟阵的基交换保证按费用排序贪心最优;非拟阵问题仍可用交换论证。
- Kruskal 是图拟阵上的实例,选择模型给出它的统一解释。
-
单独打开
拟阵是带交换公理的独立集族,所有基等势。
- 遗传性与交换性让“当前独立集能否扩展成最优基”有结构可循。
- 拟阵贪心的正确性来自基交换,不是来自元素权值的特殊性质。
- 双循环拟阵、图拟阵等实例把具体可行性翻译成独立集判定。
-
单独打开
所有基等势;两个基之间可以做元素交换。
- 基交换给出“当前独立集加入 后,最优基中可删去哪个 ”。
- 配合按权排序,交换后总权不增,因此贪心步安全。
- 这是拟阵贪心正确性的核心引理。
-
单独打开
图拟阵、划分拟阵、双循环拟阵等具体结构。
- 图拟阵:无环边集,Kruskal 是直接实例。
- 划分拟阵:每组至多选一个元素。
- 双循环拟阵:伪森林,对应 JSC2019 Qual E 的可行选择。
-
单独打开
按利润从大到小选择任务,并放在截止期前的最晚空位。
- 可准时任务集构成调度拟阵,因此按利润降序的贪心是安全的。
- 并查集维护每个时刻之前的最大空位;没有空位就跳过。
- 与最小逾期任务的区别:这里按利润选子集,后者处理所有任务并最小化逾期数。
当前内容
知识点内容
点击左侧条目查看内容。