贪心法 Greedy

贪心算法也被称为贪婪算法，它在求解问题时总想用在当前看来是最好方法来实现。这种算法思想不从整体最优上考虑问题，仅仅是在某种意义上的局部最优求解。虽然贪心算法并不能得到所有问题的整体最优解，但是面对范围相当广泛的许多问题时，能产生整体最优解或者是整体最优解的近似解。由此可见，贪心算法只是追求某个范围内的最优，可以称之为“温柔的贪婪”。

贪心算法从问题的某一个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出一个近似解。由贪心算法的特点和思路可看出，贪心算法存在以下 3 个问题。

• 不能保证最后的解是最优的。
• 不能用来求最大或最小解问题。
• 只能求满足某些约束条件的可行解的范围。

贪心算法的基本思路如下。

• 建立数学模型来描述问题。
• 把求解的问题分成若干个子问题。
• 对每一子问题求解，得到子问题的局部最优解。
• 把子问题的局部最优解合并成原来解问题的一个解。

实现该算法的基本过程如下。

• 从问题的某一初始解出发。
• while 能向给定总目标前进一步。
• 求出可行解的一个解元素。
• 由所有解元素组合成问题的一个可行解。