知识卡片

普通读书笔记卡 · 3624.a.1.b

最早结束活动可进入最优解

理解等级:高级

按结束时间选择最早结束的兼容活动,可得到某个最优活动集合:取任一最优集合的首个活动,用结束不更晚的候选替换它,后续活动仍兼容,集合大小不变。

这是针对该问题的交换论证,而非任意最早结束规则都正确。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第15章 贪心算法 · 查看原书依据

      If aj ≠ am, let the set be Ak but substituting am for aj. The activities in are compatible, which follows because the activities in Ak are compatible, aj is the first activity in Ak to finish, and fm ≤ fj.

    参考来源

    - 位置:《算法导论(第4版)》第 15 章《贪心算法》(`OEBPS/chapter015.xhtml`,文本字符 [5000, 15000))。 - 结论依据:定理 15.1 的证明用最早结束活动替换最优解首项,保持兼容性和解的大小。 - 原始内容:If a j ≠ a m , let the set be A k but substituting a m for a j . The activities in are compatible, which follows because the activities in A k are compatible, a j is the first activity in A k to finish, and f m ≤ f j .