3.4.1 贪心算法基础

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

（1）不能保证最后的解是最优的。

（2）不能用来求最大解或最小解问题。

（3）只能求满足某些约束条件的可行解的范围。

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

（1）建立数学模型来描述问题。

（2）把求解的问题分成若干个子问题。

（3）对每一子问题求解，得到子问题的局部最优解。

（4）把子问题的局部最优解合并成原来问题的一个解。

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

（1）从问题的某一初始解出发。

（2）while能向给定总目标前进一步。

（3）求出可行解的一个解元素。

（4）由所有解元素组合成问题的一个可行解。