软件设计师考试 | 第八章 算法设计与分析 | 贪心法

（一）贪心法的基本思想

和动态规划法一样，贪心法也经常用于解决最优化问题。与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。

贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。

用贪心法求得最优解的问题中一般具有的两个重要的性质：

• 最优子结构
  当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。
• 贪心选择性质
  指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。

（二）贪心法的典型实例

贪心法的典型实例有：活动选择问题，背包问题。

活动选择问题是指若干个具有竞争性的活动要求互斥使用某一公共资源时如何选择最大的相容活动集合。