视频字幕
贪心算法是一种在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优的算法策略。贪心算法的特点包括：局部最优选择、不回溯或重新考虑、简单高效，但不一定能得到全局最优解。图中红色路径展示了贪心选择，而绿色路径展示了真正的最优解。
贪心算法的工作原理可以分为三个基本步骤：首先，将问题分解为若干个子问题；其次，对每个子问题做出局部最优选择；最后，将这些局部最优选择组合成最终解。需要注意的是，贪心算法不保证找到全局最优解，但在许多问题中能够得到接近最优的解。以硬币找零问题为例，当我们需要找零41美分时，贪心算法会先选择面值最大的25美分硬币，然后是10美分，接着是5美分，最后是1美分，总共使用4个硬币。这种方法在美国硬币系统中恰好能得到最优解，但在其他硬币系统中可能不是最优的。
贪心算法在实际中有许多应用，包括最小生成树算法如Kruskal和Prim算法，单源最短路径的Dijkstra算法，哈夫曼编码，活动选择问题和区间调度问题等。以活动选择问题为例，我们需要在不重叠的情况下安排最多的活动。这里有6个活动，每个活动有不同的开始和结束时间。贪心策略是按照活动的结束时间进行排序，然后每次选择结束最早且与已选活动不冲突的活动。首先选择活动A，它在时间0到2；然后选择活动C，它在时间2到5；接着选择活动E，它在时间5到7；最后考虑活动F，但由于它与活动E有冲突，所以不能选择。因此，最多可以安排3个活动：A、C和E。这种贪心策略能够保证找到最优解。
贪心算法有其优点和缺点。优点包括：简单易实现，时间复杂度和空间复杂度通常较低。缺点则包括：不一定能得到全局最优解，需要问题具有贪心选择性质和最优子结构。与动态规划相比，贪心算法基于局部最优决策，而动态规划则考虑全局最优；贪心算法的时间和空间复杂度通常较低，而动态规划则较高；贪心算法适用于有贪心选择性质的问题，而动态规划适用于有重叠子问题的情况。让我们看一个贪心算法失效的例子：在硬币面值为1元、3元和4元的系统中找零6元。贪心算法会先选择面值最大的4元硬币，然后需要两个1元硬币，总共需要3个硬币。但最优解是选择两个3元硬币，总共只需要2个硬币。这个例子说明贪心算法并不总是能得到全局最优解。
总结一下，贪心算法是一种在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优的算法策略。贪心算法的核心是局部最优选择，它不会回溯或重新考虑之前的决策。贪心算法适用于具有贪心选择性质和最优子结构的问题，常见应用包括最小生成树、单源最短路径、活动选择问题等。贪心算法的优点是简单高效，时间和空间复杂度通常较低，但缺点是不保证得到全局最优解。在实际应用中，我们需要根据问题的特性来判断是否适合使用贪心算法。