貪心算法：貪心算法是什麼？找零錢問題實例講解

貪心算法是每步選擇當前最優（局部最優）以期望全局最優的算法，核心是滿足“貪心選擇性質”——每步局部最優能導致全局最優。經典應用如找零錢：以25、10、5、1分硬幣爲例，找67分時，按從大到小逐步取25×2（50分）、10×1（10分）、5×1（5分）、1×2（2分），共6枚，驗證爲最優。其侷限性在於，若問題不滿足貪心選擇性質（如硬幣面額[1,3,4]找6分），貪心可能失效（貪心取4+1+1=3枚，最優爲3+3=2枚）。適用場景包括硬幣面額合理（如25、10、5、1）、活動安排（選最早結束活動）等。總之，貪心算法簡單直觀高效，但僅適用於滿足貪心選擇性質的問題，不保證所有問題全局最優。