# 貪婪算法 > 原文： [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)