视频字幕
贪心算法是一种在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优的算法策略。它的特点包括：局部最优选择、不回溯、简单高效，但不保证全局最优。在图中，蓝色路径展示了贪心策略，每一步都选择向终点靠近最多的方向移动；而绿色路径是真正的最优路径，通过对角线直接移动到终点。这个例子说明了贪心算法可能无法得到全局最优解。
贪心算法适用于多种问题场景，包括活动选择问题、哈夫曼编码、最小生成树和单源最短路径等。要使贪心算法能够得到全局最优解，问题必须满足两个关键条件：贪心选择性质和最优子结构性质。图中展示了活动选择问题的例子，我们需要在一系列活动中选择最多的互不冲突的活动。贪心策略是按照活动的结束时间排序，每次选择结束最早且与已选活动不冲突的活动。这样，我们选出了活动1、活动4、活动8和活动11，这确实是最优解。
让我们通过一个具体的例子来理解贪心算法：找零钱问题。假设我们需要用最少数量的硬币找零25元，可用的硬币面值有1元、5元、10元和20元。贪心策略是每次选择不超过剩余金额的最大面值硬币。首先，我们选择一枚20元硬币，剩余5元；然后选择一枚5元硬币，剩余0元。这样，我们总共使用了2枚硬币完成找零。在这个例子中，贪心算法确实得到了最优解。但需要注意的是，如果硬币面值设置不同，比如有1元、4元、6元时，贪心算法可能无法得到最优解，这就是贪心算法的局限性。
贪心算法虽然简单高效，但也存在明显的局限性。首先，贪心算法不一定能得到全局最优解；其次，它要求问题满足特定性质；最后，我们通常难以提前验证贪心算法的结果是否最优。让我们看一个反例：使用面值为1元、4元和6元的硬币找零8元。贪心策略会先选择一枚6元硬币，然后选择两枚1元硬币，总共使用3枚硬币。但最优解是使用两枚4元硬币，只需2枚硬币。这个例子说明，贪心算法在某些情况下会失效，而动态规划等算法则能考虑所有可能的组合，找到真正的最优解。
总结一下贪心算法的要点：贪心算法是一种在每一步选择中都采取当前状态下最优的选择，希望最终得到全局最优解的算法策略。它的特点是局部最优选择、不回溯、简单高效，但不保证全局最优。贪心算法适用于活动选择问题、哈夫曼编码、最小生成树、单源最短路径等场景。要使贪心算法能够得到全局最优解，问题必须具有贪心选择性质和最优子结构性质。在实际应用中，我们需要根据问题特性判断是否适合使用贪心算法，必要时考虑动态规划等其他算法。