Greedy Algorithm

贪心算法（Greedy Algorithm） 指每一步都按某种指标的最优解进行操作，不考虑整体。因此贪心算法并不总是适用，可能造成局部最优，需要证明正确性。^[1]

适用范围

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。^[2]

证明

贪心算法有两种证明方法：反证法和归纳法。一般情况下，一道题只会用到其中的一种方法来证明。

反证法：如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。
归纳法：先算得出边界情况（例如 $n = 1$ ）的最优解 $F_{1}$ ，然后再证明：对于每个 $n$ ， $F_{n + 1}$ 都可以由 $F_{n}$ 推导出结果。

Wikipedia

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.^[1:1]