贪心算法

贪心算法是一种常见的解决优化问题的算法，其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心的做出局部最优的决策，以期获得全局最优解。 贪心算法和动态规划都常用于解决优化问题。它们之间存在一些相似之处，比如都依赖最优子结构性质，但工作原理不同。 - 动态规划会根据之前阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解 - 贪心算法不会考虑过去的决策，而是一路向前的进行贪心选择，不断缩小问题的范围，直到问题被解决。

贪心算法的优点和局限性

贪心算法不仅操作直接，实现简单，而且通常效率也很高。 一般情况下，贪心算法的适用情况分以下两种： 1. 可以保证找到最优解：贪心算法在这种情况下往往是最优解，因为它往往比回溯，动态规划更高效 2. 可以找到近似最优解：贪心算法在这种情况下也是可用的。对于很多复杂问题来说，寻找全局最优解非常困难，能以比较高效找到次优解也是非常不错的。

贪心算法特性

什么样的问题适合使用贪心算法求解呢？ 相比较于动态规划，贪心算法的使用条件更加苛刻，其主要关注问题的两个性质。 - 贪心选择性质：只有当局部最优始终可以导致全局最优解时，贪心算法才能保证得到最优解。 - 最优子结构：原问题的最优解包含子问题的最优解。

贪心算法解题步骤

贪心问题的解决流程答题可以分为一下三步： 1. 问题分析：梳理与理解问题特性，包括状态定义，优化目标和约束条件等。这一步在回溯和动态规划中有所涉及 2. 确定贪心策略：确定如何在每一步中做出贪心选择。这个策略能够在每一步减小问题的规模，并最终解决整个问题。 3. 正确性证明：通常需要证明问题具有贪心选择性质的最优子结构。这个步骤可能需要用到数学证明，例如归纳法或反证法等。 确定贪心策略是求解问题的核心步骤，但是实施起来可能并不容易，主要有以下原因： - 不同问题的贪心策略的差异较大。对于许多问题来说，贪心策略比较浅显，我们通过一些大概的思考与尝试就能得出。而对于一些复杂问题，贪心策略可能非常隐蔽，这种情况就非常考验个人的解题经验与算法能力了。 - 某些贪心策略具有较强的迷惑性。当我们满怀信心设计好贪心策略，写出解题代码并提交运行，很可能发现部分测试样例无法通过。这是因为设计的贪心策略只是“部分正确”的。 为了保证正确性，我们应该对贪心策略进行严谨的数据证明，通常需要用到反证法或数学归纳法。