文档介绍：第四章 贪心(tānxīn)方法
第一页，共83页。
2021/10/21
本章(běn zhānɡ)教学要求及重点难点
理解贪心方法的基本思想
掌握背包问题的求解方法
掌握带有限期(xiànqī)的作业排序的基本方法
掌握用贪心方法求解单源点最短路径的基本方法。
重点：用贪心方法求背包问题及带有限期(xiànqī)作业排序；
难点：用贪心方法求单源点最短路径。
第二页，共83页。
2021/10/21
一般(yībān)方法
1. 问题的一般特征
问题有n个输入，问题的解是由这n个输入的某个子集组成，这个子集必须满足某些事先给定的条件。
约束条件：子集必须满足的条件；
可行(kěxíng)解：满足约束条件的子集；可行(kěxíng)解可能不唯一；
目标函数：用来衡量可行(kěxíng)解优劣的标准，一般以函数的形式给出；
最优解：能够使目标函数取极值（极大或极小）的可行(kěxíng)解。
分类：根据描述问题约束条件和目标函数的数学模型的特性和问题的求解方法的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。
——最优化问题求解
贪心方法：一种改进的分级的处理方法，可对满足上述特征的某些问题方便地求解。
第三页，共83页。
2021/10/21
例[找零钱] 一个小孩买了价值少于1元的糖，并将1元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供数目不限的面值为25分、10分、5分及1分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。
选择硬币时所采用的贪心算法如下：每一次选择应使零钱数尽量增大。为确保解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。
假设需要找给小孩67分，首先入选的是两枚25分的硬币，第三枚入选的不能是25分的硬币，否则将不可行（零钱总数超过67分），第三枚应选择10分的硬币，然后是5分的，最后加入两个1分的硬币。
贪心算法有种直觉的倾向，在找零钱时，直觉告诉(ɡào sù)我们应使找出的硬币数目最少（至少是接近最少的数目）
第四页，共83页。
2021/10/21
2. 贪心方法的一般策略
问题(wèntí)的一般特征：问题(wèntí)的解是由n个输入的、满足某些事先给定的条件的子集组成。
1）一般方法
根据题意，选取一种度量标准。然后按照这种度量标准对n个输入排序，并按序一次输入一个量。
如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的新的部分解。
2）贪心方法
这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法
注：
贪心解 最优解
直接将目标函数作为量度标准也不一定能够得到问题(wèntí)的最优解
3）使用贪心策略求解的关键
选取能够得到问题(wèntí)最优解的量度标准。
第五页，共83页。
2021/10/21
3. 贪心方法的抽象化控制(kòngzhì)描述
procedure GREEDY(A,n)
//A(1:n)包含n个输入//
solution←Φ //将解向量solution初始化为空//
for i←1 to n do
x←SELECT(A) //按照度量标准，从A中选择一个输入，其值赋予x
并将之从A中删除//
if FEASIBLE(solution,x) then //判定x是否可以包含在解向量中，
即是否能共同构成可行解//
solution←UNION(solution,x) //将x和当前的解向量合并成新的解
向量，并修改目标函数/