贪心算法课件1.ppt

1、贪心方法的基本思想 贪心是一种解题策略，也是一种解题思想 使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优 利用贪心策略解题，需要解决两个问题：该题是否适合于用贪心策略求解 如何选择贪心标准，以得到问题的最优解 【引例引例】在一个NM的方格阵中，每一格子赋予一个数（即为权），规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。我们以23的矩阵为例：若按贪心策略贪心策略求解，所得路径为：1346；若按动态规划动态规划求解，所得路径为：12106。贪心法的特点贪心法的特点 1.贪心选择性质：贪心选择性质：算法中每

2、一步选择都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未做的选择。2.最优子结构性质：最优子结构性质：算法中每一次都取得了最优解(即局部最优解)，要保证最后的结果最优，则必须满足全局最优解包含局部最优解。但并不是所有具有最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法动态规划（例如“0-1背包问题”与“部分背包问题”）【问题问题1】部分背包问题部分背包问题 给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。【分析分析】

3、因为每一个物品都可以分割成单位块，单位块的利益越大，显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。【问题问题2】0/1背包问题背包问题 给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。【分析分析】按贪心法：每次选价格最大的装载。很明显有反例：设N=3,卡车最大载重量是100,三种动物A、B、C的重量分别是40,50,70,其对应的总价值分别是80、1

4、00、150。贪心策略与其他算法的区贪心策略与其他算法的区别别 1.贪心与递推：贪心与递推：与递推不同的是，贪心法中推进的每一步不是依据某一固定的递推式，而是当前看似最佳的贪心决策，不断的将问题归纳为更加小的相似的子问题。所以归纳、分析、选择正确合适的贪心策略，是正确解决贪心问题的关键。2.贪心与动态规划：贪心与动态规划：与动态规划不同的是，贪心是鼠目寸光；动态规划是统揽全局。几个简单的贪心例子几个简单的贪心例子 例题例题1：删数问题：删数问题 键盘输入一个高精度的正整数n（n从取3张牌放到(9 11 10 10)-从取1张牌放到(10 10 10 10）。【试题分析试题分析】我们要使移动次数

5、最少，就是要把浪费降至零。通过对具体情况的分析，可以看出在某相邻的两堆之间移动两次或两次以上，是一种浪费，因为我们可以把它们合并为一次或零次。【思路点拨思路点拨】如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成0，那就意味着成功了一半！从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆,步数是一样的。注意最左边的0和最右边的0不能算在内，如0,0,1,-3,4,0,-1,0,0 若题目中的纸牌排成一个环状，应如何处理呢？其中n=1000。有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。求使所

6、有人获得均等糖果的最小代价。【数据规模数据规模】对于30%的数据n=1000；对于100%的数据n=1000000 贪心的经典应用贪心的经典应用（一）、三个区间上的问题（一）、三个区间上的问题 1、选择不相交区间问题、选择不相交区间问题 2、区间选点问题、区间选点问题 3、区间覆盖问题、区间覆盖问题（二）、两个调度问题（二）、两个调度问题 1、流水作业调度问题、流水作业调度问题 2、带限期和罚款的单位时间任务调度、带限期和罚款的单位时间任务调度（三）（三）Huffman编码编码（四）最优合并问题最优合并问题 给定给定n个开区间个开区间(ai,bi)，选择尽量多个区间，使，选择尽量多个区间，使得

7、这些区间两两没有公共点。得这些区间两两没有公共点。【算法实现算法实现】首先按照b1=b2=bn的顺序排序，依次考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。【正确性正确性】：如果不选b1，假设第一个选择的是bi，则如果bi和b1不交叉则多选一个b1更划算；如果交叉则把bi换成b1不影响后续选择。设有设有n个活动的集合个活动的集合E=1,2,.,n，其中每个活动，其中每个活动都要求使用同一资源，如演讲会场等，而在同一都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间都有一

8、个要求使用该资源的起始时间si和一个结和一个结束时间束时间fi，且，且sifi。如果选择了活动。如果选择了活动i，则它在半，则它在半开时间区间开时间区间si,fi)内占用资源。若区间内占用资源。若区间si,fi)与区与区间间sj,fj)不相交，则称活动不相交，则称活动i与活动与活动j是相容的。是相容的。也就是说，当也就是说，当fi=si时，活动时，活动i与活动与活动j相相容。选择出由互相兼容的活动组成的最大集合。容。选择出由互相兼容的活动组成的最大集合。给定给定n个闭区间个闭区间ai,bi，在数轴上选尽量少的，在数轴上选尽量少的点，使得每个区间内都至少有一个点（不同区点，使得每个区间内都至少有

9、一个点（不同区间内含的点可以是同一个）。间内含的点可以是同一个）。【算法算法】：首先按照b1=b2=bn排序。每次标记当前区间的右端点X，并右移当前区间指针，直到当前区间不包含X，再重复上述操作。例题例题6：种树（：种树（NOIP模拟模拟试题）试题）一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号为1.n。每个块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码b,e,t。这三个数表示该居民想在b和e之间最少种t棵树。当然，b=e,居民必须保证在指定地区不能种多于地区被分割成块数的树，即要求t=s的的bi的最大值即可。的最大值即可

10、。例题例题7：区间（：区间（SDOI2005）现给定n个闭区间ai,bi，1=i=n。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间a,b和c,d是按照升序排列的，那么我们有ab=c=d。任务：读入这些区间，计算满足给定条件的不相交闭区间，并把这些区间按照升序输出。练习试题：喷水装置练习试题：喷水装置 有一块草坪，长为L，宽为w；在它的中心线上装有n个点状的喷水装置，效果是让以它为中心半径为ri的圆被润湿，选择尽量少的喷水装置把整个草坪全部润湿。旅行家的预算 一个旅行家想驾驶汽车以最少的费用从

11、一个城市到另一个城市（假设出发时油箱时空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途加油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。样例：Input D1=275.6 C=11.9D2=27.4 P=2.8 N=2 油站号I离出发点的距离Di每升汽油价格Pi1102.02.92220.02.2 Output 26.95（该数据表示最小费用）分析：需要考虑如下问题：出发前汽车的油箱是空的，故汽车必须

12、在起点（1号站）处加油。加多少油？汽车行程到第几站开始加油，加多少油？可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以归结为原问题的子问题。因此，原问题关键在于如何确定下一个加油站。通过分析，我们可以选择这样的贪心标准：对于加油站I，下一个加油站J可能第一个是比油站I油价便宜的油站，若不能到达这样的油站，则至少需要到达下一个油站后，继续进行考虑。对于第一种情况，则油箱需要（d（j）-d（i）/m加仑汽油。对于第二种情况，则需将油箱加满。算法 I:=1 汽车出发设定为第1个加油站L:=C*D2；油箱装满油能行驶的距离repeat 在L距离以内，向后找第一个油价比I站便宜的加油站J；if J存在 then if I站剩余油能到达J then 计算到达J站的剩油 else 在I站购买油，使汽车恰好能到达J站 else 在I站加满油；I:=J；汽车到达J站until 汽车到达终点；贪心方法的推广贪心方法的推广 贪心与其它算法结合 搜索的最优化剪枝（生日蛋糕）优化动态规划（Peter的快餐店）贪心方法与解题策略 最优方法不一定是最好方法 想不到最优解法就用较优解法 贪心作为一种解题思路，虽然有时无法证明它的正确性，但在无法找到其他算法的时候，不失为一种好方法。并且，贪心与其他算法的结合，可以对其他算法起到优化作用。