认识贪心算法

介绍

贪心算法是对完成一件事情的方法的描述，贪心算法每一次都做出当前看起来最好的选择，而不用考虑其它可能的选择。

贪心算法的学习可以与动态规划算法进行比较，看看它到底比动态规划算法少考虑了哪些子问题，为什么可以少考虑那些子问题，而每次只专注于求解一个子问题，通过逐步递推得到原问题的答案。

贪心算法的应用场景：解决一个问题需要多个步骤，每一个步骤有多种选择。可以使用贪心算法解决的问题，每一步只需要解决一个子问题，只做出一种选择，就可以完成任务。

贪心算法与回溯算法、动态规划的区别: 「解决一个问题需要多个步骤，每一个步骤有多种选择」这样的描述我们在「回溯算法」「动态规划」算法中都会看到。它们的区别如下：

• 「回溯算法」需要记录每一个步骤、每一个选择，用于回答所有具体解的问题；
• 「动态规划」需要记录的是每一个步骤、所有选择的汇总值（最大、最小或者计数）；
• 「贪心算法」由于适用的问题，每一个步骤只有一种选择，一般而言只需要记录与当前步骤相关的变量的值。

如图所示：

动态规划：

:::details 点击查看图片 :::

贪心算法：

:::details 点击查看图片 :::

可以使用「贪心算法」的问题需要满足的条件:

• 最优子结构：规模较大的问题的解由规模较小的子问题的解组成，区别于「动态规划」，可以使用「贪心算法」的问题「规模较大的问题的解」只由其中一个「规模较小的子问题的解」决定；
• 无后效性：后面阶段的求解不会修改前面阶段已经计算好的结果；
• 贪心选择性质：从局部最优解可以得到全局最优解。