貪心算法（英語：greedy algorithm），又稱貪婪算法，是一種在每一步選擇中都采取在當前狀態下最好或最優（即最有利）的選擇，從而希望導致結果是最好或最優的算法。比如在旅行推銷員問題中，如果旅行員每次都選擇最近的城市，那這就是一種貪心算法。 <br> 貪心算法在有最優子結構的問題中尤為有效。最優子結構的意思是局部最優解能決定全局最優解。簡單地說，問題能夠分解成子問題來解決，子問題的最優解能遞推到最終問題的最優解。 <br> 貪心算法與動態規劃的不同在于它對每個子問題的解決方案都做出選擇，不能回退。動態規劃則會保存以前的運算結果，并根據以前的結果對當前進行選擇，有回退功能。 <br> 貪心法可以解決一些最優化問題，如：求圖中的最小生成樹、求哈夫曼編碼……對于其他問題，貪心法一般不能得到我們所要求的答案。一旦一個問題可以通過貪心法來解決，那么貪心法一般是解決這個問題的最好辦法。由于貪心法的高效性以及其所求得的答案比較接近最優結果，貪心法也可以用作輔助算法或者直接解決一些要求結果不特別精確的問題。 <br> ### 算法架構： ``` 從問題的某一初始解出發； while （能朝給定總目標前進一步） {? ??? 利用可行的決策，求出可行解的一個解元素； } 由所有解元素組合成問題的一個可行解； ```