视频字幕
贪心算法是一种简单而直观的算法策略。想象一下你面前有一盘大小不同的饼干，贪心算法就像是你每次都只挑眼前能看到的最大的那块饼干吃掉。它不会考虑未来的后果，只关心当下哪个选择最好。贪心算法的核心思想就是在解决问题的每一步，都做出当前看起来最好的选择，希望通过一系列这样的局部最优选择，最终能得到一个全局最优的解。
贪心算法的执行流程可以用流程图清晰地表示。首先从问题的初始状态开始，然后判断问题是否已经解决。如果问题已经解决，就输出当前的解并结束算法。如果问题还没有解决，就根据贪心策略做出当前看起来最优的选择，然后更新问题的状态，缩小问题的规模，接着回到判断步骤继续下一轮选择。这个过程会一直重复，直到问题完全解决为止。
让我们通过找零钱问题来演示贪心算法的工作过程。假设需要找给顾客48分钱，我们有25分、10分、5分、1分四种面额的硬币。贪心策略是每次都选择当前剩余金额下能用的最大面额硬币。首先选择25分硬币，剩余23分。然后选择10分硬币，剩余13分。再选择10分硬币，剩余3分。接着选择1分硬币三次，最终用6枚硬币完成找零。
贪心算法在计算机科学中有广泛的应用场景。主要包括找零钱问题、最小生成树算法如Prim和Kruskal算法、最短路径算法如Dijkstra算法、活动选择问题和分式背包问题等。这里演示的是最小生成树问题，贪心策略是每次选择权重最小且不形成环的边。贪心算法能够成功应用的关键在于问题必须具备贪心选择性质和最优子结构性质。只有满足这些条件，贪心算法才能保证找到最优解。
总结一下，贪心算法是一种简单直观、效率高且易于实现的算法策略。它的核心思想就像吃饼干时每次都选最大的那块一样，在每一步都做出当前看起来最好的选择。但是要注意，贪心算法并不总是能得到最优解，需要验证问题是否具备贪心选择性质和最优子结构。在适用的场景下，如找零钱问题和最短路径问题，贪心算法表现优秀。但在不适用的场景下，如0/1背包问题，就需要使用其他算法。记住贪心算法的精髓：局部最优不等于全局最优，使用前要仔细分析问题特性。