介绍

• 贪心算法（Greedy Algorithm）是一种在解决问题时所采用的逐步构建解决方案的策略。它在每一步选择中都采取当前状态下最优或最有利的选择，而不管这个选择在全局范围内是否最优。简单来说，贪心算法总是做出看起来最好的选择，期望通过一系列的局部最优选择最终得到全局最优解。

• 贪心算法的特点

  • 局部最优：贪心算法在每一步都选择当前状态下最优的操作。
  • 全局最优：通过局部最优的选择，贪心算法期望最终能得到全局最优解。但贪心算法并不总是能保证得到全局最优解。
  • 不回溯：一旦作出某个选择，贪心算法不会回头更改以前的选择。它不会像动态规划或回溯算法那样存储之前的状态。

• 应用场景

  • 最优子结构性质：一个问题具有最优子结构，如果问题的最优解包含其子问题的最优解。贪心算法可以通过解决子问题来构建全局最优解。
  • 贪心选择性质：每一步的局部最优选择可以构成问题的全局最优解。

• 常见的贪心算法例子

  • 活动选择问题：选择最多的活动在一个时间段内参加，要求选出的活动互不冲突。
  • 最小生成树问题：Kruskal和Prim算法都利用贪心思想构造图的最小生成树。
  • Huffman编码：基于字符出现的频率，构建最优的前缀编码。
  • 找零问题：在商店找零时，使用最少数量的硬币来找出指定金额。

• 贪心算法的局限性：贪心算法不是万能的，只有当问题满足贪心选择性质和最优子结构性质时，才能确保贪心算法得到的解是全局最优的。在某些情况下，贪心算法得到的解可能不是最优的，因为它只考虑了局部的最优解，没有考虑全局的情况。