贪心算法

• 经典应用

  • 霍夫曼编码
  • Prim 和 Kruskal 最小生成树算法
  • Dijkstra 单源最短路径算法

• 贪心算法步骤

  • 当我们看到这类问题的时候，首先要联想到贪心算法

    • 针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
    • 当前一步的选择不会影响下一步的选择的时候，考虑贪心算法。
      • 例如背包问题，就一直找最大，填满背包即可。可以用贪心算法
      • 例如0-1背包问题，一直找最大的话，会限制背包空间，从而影响下一件物品的选择，不适合用贪心
      • 例如最短路径问题，一直找最小的话，一般都不是最小，因为选择了最小路径之后，接下来要选择的路会受到影响。

  • 我们尝试看下这个问题是否可以用贪心算法解决

  • 我们举几个例子看下贪心算法产生的结果是否是最优的

    • 大部分情况下，举几个例子验证一下就可以了。