下载掌阅APP，畅读海量书库
立即打开
我们在遇到具体问题时，往往分不清对哪些问题可以用贪心算法，对哪些问题不可以用贪心算法。实际上，如果问题具有两个特性：贪心选择性质和最优子结构性质，则可以用贪心算法。
（1）贪心选择性质。贪心选择性质指原问题的整体最优解可以通过一系列局部最优的选择得到。应用同一规则，将原问题变为一个相似的、但规模更小的子问题，而后的每一步都是当前最优的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。运用贪心算法解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后面贪心算法图解中得到深刻的体会。
（2）最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题是否可以用贪心算法求解的关键。例如原问题 S= { a 1 , a 2 ,…, a i ,…, a n }，通过贪心选择选出一个当前最优解{ a i }之后，转化为求解子问题 S -{ a i }，如果原问题的最优解包含子问题的最优解，则说明该问题满足最优子结构性质。
贪心算法的求解步骤如下。
（1）贪心策略。指确定贪心策略，选择当前看上去最好的一个。比如挑选苹果，如果你认为个头大的是最好的，那么每次都从苹果堆中拿一个最大的作为局部最优解，贪心策略就是选择当前最大的苹果。如果你认为最红的苹果是最好的，那么每次都从苹果堆中拿一个最红的，贪心策略就是选择当前最红的苹果。因此根据求解目标的不同，贪心策略也会不同。
（2）局部最优解。指根据贪心策略，一步步地得到局部最优解。比如第1次选一个最大的苹果放起来，记为 a 1 ；第2次再从剩下的苹果中选择一个最大的苹果放起来，记为 a 2 ，以此类推。
（3）全局最优解。指把所有的局部最优解都合成原问题的一个最优解{ a 1 , a 2 ……}。