贪心算法：贪心算法是什么？找零钱问题实例讲解

贪心算法是每步选择当前最优（局部最优）以期望全局最优的算法，核心是满足“贪心选择性质”——每步局部最优能导致全局最优。经典应用如找零钱：以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）、活动安排（选最早结束活动）等。总之，贪心算法简单直观高效，但仅适用于满足贪心选择性质的问题，不保证所有问题全局最优。