# 贪婪算法 > 原文： [https://www.programiz.com/dsa/greedy-algorithm](https://www.programiz.com/dsa/greedy-algorithm) #### 在本教程中，您将学习什么是贪婪算法。 此外，您还会找到一个贪婪方法的示例。 贪心算法是一种通过选择当前可用的最佳选项来解决问题的方法，而无需担心将来会带来什么结果。 换句话说，本地最佳选择旨在产生全局最佳结果。 对于所有问题，该算法可能都不是最佳选择。 在某些情况下，它可能会产生错误的结果。 该算法永远不会返回来扭转所做出的决定。 该算法以自顶向下的方式工作。 该算法的主要优点是： 1. **该算法更容易描述**。 2. 与其他算法相比，该算法的**性能更好**（但并非在所有情况下）。 * * * ## 可行的解决方案 一种可行的解决方案是为问题提供最佳解决方案的解决方案。 * * * ## 贪婪算法 1. 首先，解决方案集（包含答案）为空。 2. 在每个步骤中，将一个项目添加到解决方案集中。 3. 如果解决方案集可行，则保留当前项目。 4. 否则，该项目将被拒绝，不再考虑。 * * * ## 贪婪方法示例 ``` Problem: You have to make a change of an amount using the smallest possible number of coins. Amount: $28 Available coins: $5 coin $2 coin $1 coin ``` **解决方案**： 1. 创建一个空的`solution-set = {}`。 2. `coins = {5, 2, 1}` 3. `sum = 0` 4. 当`sum≠38`时，请执行以下操作。 5. 从`coins`中选择一个硬币`C`，使得`sum + C < 28`。 6. 如果`C + > 28`之和，则不返回任何解。 7. 否则，`sum = sum + C`。 8. 将`C`添加到`solutionSet`中。 在前 5 次迭代之前，解决方案集包含 5 个 5 美元个硬币。 之后，我们得到 1 个 2 美元硬币，最后得到 1 个 1 美元硬币。 * * * ## 贪婪算法应用 * [选择排序](/dsa/selection-sort) * [背包问题](https://en.wikipedia.org/wiki/Knapsack_problem) * [最小生成树](/dsa/spanning-tree-and-minimum-spanning-tree) * [单源最短路径问题](https://en.wikipedia.org/wiki/Shortest_path_problem) * 作业调度问题 * [Prim 的最小生成树算法](/dsa/prim-algorithm) * [Kruskal 的最小生成树算法](/dsa/kruskal-algorithm) * [Dijkstra 的最小生成树算法](/dsa/dijkstra-algorithm) * [霍夫曼编码](/dsa/huffman-coding) * [Ford-Fulkerson 算法](/dsa/ford-fulkerson-algorithm)