贪心算法图文详解

贪心算法又称贪婪算法，是所有算法中最简单、最易实现的一种算法。

一个问题通常对应有多种算法，每种算法由多个步骤组成。贪心算法解决问题的核心思想是：算法的每一步都选择当前场景中最优的解决方案（又称局部最优解）。

举个例子，假设我们有面值分别为 1、2、5、10 的硬币，要求用尽可能少的硬币拼凑出的总面值为 18。如果采用贪心算法解决此问题，则解决方案为：

1. 选择一个面值为 10 的硬币，可最大程度解决问题，剩余需要拼凑的面值数为 8；

2. 选择一个面值为 5 的硬币，可最大程度解决问题，剩余需要拼凑的面值数为 3；

3. 选择一个面值为 2 的硬币，可最大程度解决问题，剩余需要拼凑的面值数为 1；

4. 选择一个面值为 1 的硬币。

贪心算法每一步都选择的是当前所允许的最大面值的硬币（即局部最优解），整个解决方案也是最优的。

注意，贪心算法并不是在任何场景中都可以得出最优的解决方案。比如，有面值分别为 1、7、10 的硬币，要求用尽可能少的硬币拼凑出的总面值为 15。如果采用贪心算法，则解决方案为：

1. 选择一个面值为 10 的硬币，剩余面值为 5；

2. 选择一个面值为 1 的硬币，剩余面值为 4；

3. 选择一个面值为 1 的硬币，剩余面值为 3；

4. 选择一个面值为 1 的硬币，剩余面值为 2；

5. 选择一个面值为 1 的硬币，剩余面值为 1；

6. 选择一个面值为 1 的硬币。

贪心算法使用了“10+1+1+1+1+1”共 6 枚硬币，但实际上，最优的解决方案只需要“7+7+1”共 3 枚硬币。所以，贪心算法追求的是局部最优解，它并不关心设计的整个解决方案是否最优。

贪心算法的实际应用

贪心算法可用于解决很多实际问题，例如：

• 部分背包问题；

• 使用克鲁斯卡尔算法求最小生成树；

• 使用迪杰斯特拉算法求两个顶点之间的最短路径。

我们会在后续的文章中，一一为您讲解这些问题。