搜索
ACM程序设计第十讲-贪心算法湖南工学院张新玉zhangxinyu247@163.com引言[引言]贪婪是一种人类本能的东西，贪心算法也是最接近人类日常思维的一种解题策略。其实，在解决一些日常问题时，我们本能就怀着对目标最直观、最简单、最高效的思路，其中往往就带有贪心思想的影子。虽然它不能保证求得的最后解一定是最佳的，但是它可以为某些问题确定一个可行性范围。在某些范围内，贪心算法是我们的最佳选择。引例——找零钱[问题描述]假设提供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币。一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设小孩买了33美分的糖果（需要找给小孩67美分）找钱的方法：25+25+10+5+1+1我们有种直觉的倾向：在找零钱时，直觉告诉我们使用面值大的硬币，剩余的金额就越少。什么是贪心算法？将问题的求解过程看作是一系列选择，每次选择一个输入，每次选择都是当前状态下的最好选择(局部最优解)。每作一次选择后，所求问题会简化为一个规模更小的子问题。从而通过每一步的最优解逐步达到整体的最优解。[贪心算法的示意图]其中：·红箭头表示当前最优决策；·蓝箭头表示其他决策；·小球表示当前状态。[贪心算法基本思想：]贪心算法的概念这样转化的直觉：使用越多的大面值的硬币，最后硬币总数就会越少[标准转化]找一个硬币的时候：找的硬币总数最少→使剩余金额最少原现顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。贪心猜想（贪心策略）贪心算法的概念从问题的某一初始解出发；while能朝给定总目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；[贪心算法步骤]真正意义要求解原问题将原问题变成更小子问题的步骤整理解【标准转化】实例——小鼠迷宫问题[问题描述]每次老鼠a可以向八个方向移动，要求到达迷宫出口b的最少步数。实例——小鼠迷宫问题[算法分析]算法：贪心策略的应用每次沿着尽可能减小到终点距离的方向走。实例——小鼠迷宫问题[问题描述]每次老鼠a可以向八个方向移动，要求到达迷宫出口b的最少步数。要求解的原问题：[a到b的路径]变成更小子问题的步骤：[移动一次]标准转化：[最小步数]-[距离最短的方向]引例——小鼠迷宫问题[变化]每次老鼠a可以向八个方向移动，不能移动到陷阱（黄色的格子），要求到达迷宫出口b的最少步数。贪心概念[最优化问题]最优化问题包含一组限制条件（约束条件）和一个目标函数（优化函数）符合限制条件的问题求解方案称为可行解，使目标函数取得最佳值（最大或最小）的可行解称为最优解。贪心概念[求解这类问题的方法]1、搜索最原始的方法是搜索（穷举）法。2、动态规划贪心概念[求解这类问题的方法]贪心法是求解这类问题的另一种常用算法。【定义】指从问题初态出发，通过若干次贪心选择而得出最优（或较优）解的一种解题方法。具体来讲，即从问题的某一个初始解出发，采用逐步构造最优解的方法向给定的目标前进。在每个局部阶段，都做出在当前看来是最优的选择，并期望通过每次所做的局部最优选择产生出一个全局最优解。贪心算法的概念请注意：贪心算法期望通过每次所做的局部最优选择产生出一个全局最优解。[面额规定问题]假设硬币面值为7元、6元、2元、1元。要找12元钱。找钱的方法：7+2+2+1找钱的方法：6+6贪心算法的概念具备贪心选择和最优子结构性质的最优化问题。每次的选择可以依赖以前作出的选择,但不能依赖于后面的选择。问题的整体最优解中包含着它的子问题的最优解。[适用问题]贪心算法的概念[贪心算法解题的一般步骤]1、设计数据找规律2、进行贪心猜想3、正确性证明（严格证明和一般证明）·严格证明：数学归纳和反证法·一般证明：列举反例4、程序实现若无法证明,此步骤可缺省例1——纪念品分组[问题描述]元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。[任务]请你编写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。例1——纪念品分组[输入格式]输入中共有n+2行。第一行中为一个整数w，表示每组纪念品价格之和的上限。第二行中为一个整数n（n=30000），表示购来的纪念品的总件数。第三行至第n+2行，每行有一个正整数pi（5=pi=w），表示所对应纪念品的价格。[输出格式]输出中仅一行为一个整数，即最少的分组数目。例1——纪念品分组[输入输出样例]输入：输出：10069902020305060708090[算法分析]例1——纪念品分组因为题目中N给出的范围太大，用搜索肯定不可行。根据题意，要求尽量将不超过两个纪念品放在一起使得分组数目最小。我们看一个简单的例子：有4个整数1、2、3、4，要求不超过两个整数形成一个分组，且分组之和不超过5，问有哪些方案？①1+2、3、4（三组）②1+3、2、4（三组）③1+4、2+3（两组）经过简单的尝试，得出最优解是（1，4）、（2，3）两组，而其它分法的答案至少是三组。[算法分析]例1——纪念品分组我们首先随便取一个礼物，如果要把它和另一个“打包”，选哪一个呢？显然，我们要选择尽量大的礼物，把盒子“装满”，为后面的分组更加有利。从这个例子，我们得到一个猜想：不断把最大的和最小的安排在一起，最后解最小！如何来实现？[算法分析]例1——纪念品分组贪心策略：首先，将所有纪念品排序；按从大到小，判断当前最大的是否能和当前最小的放在一组。若能，则放在一组，若不能，则将最大的单独放一组。如此下去，直至扫描完毕。[证明]标准转化例1——纪念品分组[贪心策略证明]证明过程如下：假设存在abcd，分组为（a，c）、（b，d）是最优解。显然，b+da+c，价值最大值为：b+d。交换后，我们可以看出：a+db+d、b+cb+d，整体的最大值在减小。不断进行这样的交换，可以保证最后得到的合法“分组”中最大值最小。同理，对于分组（a，b）和分组c（单个）、分组d（单个），也不可能在满足最大值时变换成（a，d）、（b，c）格式。[返回]2、贪心算法的特点[贪心策略]做出贪心决策的依据称为贪心策略，贪心策略一旦做出，就不可再更改。推进的每一步不是依据某一固定的递推式，而是做一个当时看似最佳的贪心选择，不断地将问题实例归纳为更小的相似子问题。所以，归纳、分析、选择正确合适的贪心策略，是正确解决贪心问题的关键。例2——歌手与小朋友照相[问题描述]歌手SJM到幼儿园跟小朋友玩，他到达的时候小朋友已经争着积木玩了。小朋友都想要更多的积木砌一个自己喜欢的图形，砌玩就可以和SJM合照。同时，SJM手上还有一些积木，他可以把手里的这些积木全部给一个小朋友，然后等该小朋友砌完后就可以收回所发的积木和该小朋友原先手里的积木。但SJM想知道他最多可以和多少个小朋友合照，你能帮助他吗？例2——歌手与小朋友照相[输入]输入第一行包括两个正整数N和S，中间用空格隔开，其中1=N=1000,1=S=10000,表示一共有N位小朋友，SJM手上有S块积木。以下有N行，每行有两个正整数，a和b(1=a=10^5,1=b=10^9),表示每个小朋友手上有的积木数量和还需要的积木数量。[输出]输出SJM最多可以和多少个小朋友合照。[输入输出样例]输入：221421输出：2例3——擂台PK[问题描述]有一天，Symbol为了与Tango一较高下，于是派出了自己的学生们与Tango的弟子们进行了比赛。双方一共会进行n轮比赛，每轮比赛双方都会派出一个人在擂台上进行激烈的PK。现在，Tango请来了你来做他的参谋：假如已经知道双方队员的战斗力数值，问如何安排Tango队队员的出场顺序才能取得最多的胜利。（注：由于裁判已被Symbol收买，若战斗力相同，则Symbol队的队员胜利）例3——擂台PK[输入]每组数据有3行。第1行，只有一个数字n，代表双方进行的比赛轮数。第2行，有n个整数，代表Tango队n个人的战斗能力。第3行，有n个整数，代表Symbol队n个人的战斗能力。[输出]Tango队最多能赢的轮数。[输入输出样例]输入：3928371958774输出：24、贪心算法的总结[贪心算法小结]贪心算法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。贪心算法的最大特点就是快，通常是线性二次式，不需要多少额外的内存。贪心算法，在程序的运行过程中无回溯过程，后面的每一步都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未做出的选择。4、贪心算法的总结[贪心算法小结]a)如何贪心贪心算法有两大难点：怎样用一个小规模的解构造更大规模的解呢?总体上，这与问题本身有关。但是大部分都是有规律的。一般而言，单纯的贪心算法是顺序处理问题的；而且每个结果是可以在处理完一个数据后即时输出的。4、贪心算法的总结[贪心算法小结]b)贪心的正确性贪心算法有两大难点：要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会与整体最优解之间有联系。因为贪心算法的适用范围并不大，而且有一部分极难证明，若是没有把握，最好不要冒险，还有其他算法会比它要保险。4、贪心算法的总结[小结]（1）归纳、分析、选择贪心准则是解决贪心问题的关键。（2）胆大心细，努力掌握。相关习题基础题：1045，1257，2021，1789进阶题：2037，4864，1969