贪心算法专题-课时2

贪心算法专题课时2:分组选择、贪心选择模型、拟阵与拟阵基定理、拟阵实例,以及单位时间任务调度。

6 个条目 · 点击条目切换内容

下载讲义 PDF
  1. 每组至多选一个带权元素,按权值降序,能选就选。

    • 可行集族对子集封闭,是选择模型的直接实例。
    • 用交换论证证明跳过和加入都是安全的;后续可用划分拟阵解释。
    单独打开
  2. 按元素代价非减处理,能加入当前可行集就加入。

    • 可行族对子集封闭时,维护已选集合与安全加入条件。
    • 拟阵的基交换保证按费用排序贪心最优;非拟阵问题仍可用交换论证。
    • Kruskal 是图拟阵上的实例,选择模型给出它的统一解释。
    单独打开
  3. 拟阵是带交换公理的独立集族,所有基等势。

    • 遗传性与交换性让“当前独立集能否扩展成最优基”有结构可循。
    • 拟阵贪心的正确性来自基交换,不是来自元素权值的特殊性质。
    • 双循环拟阵、图拟阵等实例把具体可行性翻译成独立集判定。
    单独打开
  4. 所有基等势;两个基之间可以做元素交换。

    • 基交换给出“当前独立集加入 𝑒 后,最优基中可删去哪个 𝑒′”。
    • 配合按权排序,交换后总权不增,因此贪心步安全。
    • 这是拟阵贪心正确性的核心引理。
    单独打开
  5. 图拟阵、划分拟阵、双循环拟阵等具体结构。

    • 图拟阵:无环边集,Kruskal 是直接实例。
    • 划分拟阵:每组至多选一个元素。
    • 双循环拟阵:伪森林,对应 JSC2019 Qual E 的可行选择。
    单独打开
  6. 按利润从大到小选择任务,并放在截止期前的最晚空位。

    • 可准时任务集构成调度拟阵,因此按利润降序的贪心是安全的。
    • 并查集维护每个时刻之前的最大空位;没有空位就跳过。
    • 与最小逾期任务的区别:这里按利润选子集,后者处理所有任务并最小化逾期数。
    单独打开
当前内容

知识点内容

点击左侧条目查看内容。

源码位置