【算法笔记】贪心法--介绍
2021-02-21
1 min read
- 优化子结构
若一个优化问题的优化解包含它的 子问题的优化解,则称其具有优化子结构
- 贪心选择性
若一个优化问题的全局优化解可以通过 局部优化选择得到,则该问题称为具有 贪心选择性.
使用贪心算法解决问题时:
-
设计贪心方法
-
证明贪心法的正确性(有时比设计算法更重要)
例:活动最大相容问题


(1) 证明优化子结构
活动按照结束时间已经排好序
即证明:设A是问题S的一个优化解且包含活动1,则A-{1}是问题S’(S’中最早的开始时间晚于f1)的优化解
反证法(略)
(2)证明贪心选择性
归纳法(略)