程序设计培训讲义4：贪心算法

1、程序设计培训之4：贪心算法袁辉勇2010年1月8日 贪心法也称为贪婪法。贪心法也称为贪婪法。 算法原理：算法原理：以当前情况为基础作最优选择，以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪心法不而不考虑各种可能的整体情况，所以贪心法不要回溯。要回溯。 算法优点：算法优点：因为省去了为寻找解而穷尽因为省去了为寻找解而穷尽所有可能所必须耗费的大量时间，因此算法效所有可能所必须耗费的大量时间，因此算法效率高。率高。 注意：注意：通常使用贪心算法时需要证明。通常使用贪心算法时需要证明。一、概述一、概述例例1：找零钱问题。：找零钱问题。 平时购物找钱时，为使找回的零钱的硬平时购物找钱时，

2、为使找回的零钱的硬币数最少，不考虑找零钱的所有各种发表方币数最少，不考虑找零钱的所有各种发表方案，而是从最大面值的币种开始，按递减的案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种当不足大面值币种的金额时才去考虑下一种较小面值的币种。较小面值的币种。 这就是在使用贪心法。这就是在使用贪心法。http:/ 找出一条路径，使其从左下角至右上角所经过的找出一条路径，使其从左下角至右上角所经过的权之和最大。权之和最大。分析：分析：例如下面的一个例如下面的一个23的方格阵中，每一格子都的方格阵中，每一

3、格子都填写了一个数。填写了一个数。若按若按贪心法贪心法求解，路径为：求解，路径为：1346；若按若按动态规划法动态规划法求解，路径为：求解，路径为：12106总结：总结：由于贪心策略自身的特点，使得数字由于贪心策略自身的特点，使得数字10所在的格子成为一个所在的格子成为一个“坏格子坏格子”，即运用贪心，即运用贪心策略找不到它，运用贪心策略求解的第一步策略找不到它，运用贪心策略求解的第一步（13）保证了局部最优解，却无法保证全局）保证了局部最优解，却无法保证全局最优解。最优解。故本问题不能使用贪心法来求解。故本问题不能使用贪心法来求解。 例例3 最优装载问题最优装载问题 有有n个集装箱要装上个集

4、装箱要装上1艘载重量分别为艘载重量分别为c的轮的轮船，其中第船，其中第i个集装箱的重量为个集装箱的重量为wi。最优装载问。最优装载问题要求确定在装载体积不受限制的情况下，将题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。装载方案可能不尽可能多的集装箱装上轮船。装载方案可能不唯一，约定长为唯一，约定长为n的的01字符串字符串(1:表示装表示装)以字典以字典序最大的那个为符合要求的装载方案。序最大的那个为符合要求的装载方案。输出样例输出样例1101101010010100输入样例：输入样例：3 5040 10 405 3710 30 24 35 40 枚举算法思路：枚举算法思路：

5、 这个问题可以用枚举算法来解：设立一数这个问题可以用枚举算法来解：设立一数组组x，数组每个元素，数组每个元素xi可能取值为可能取值为0或或1。如果。如果xi 为为0，则货箱，则货箱i 将不被装上船；如果将不被装上船；如果xi 为为1，则货箱则货箱 i 将被装上船。将被装上船。 贪心算法思路：贪心算法思路： 这个问题也可以用贪心算法来解：由于货箱的这个问题也可以用贪心算法来解：由于货箱的大小都一样，但货箱的重量都各不相同，故可以按照大小都一样，但货箱的重量都各不相同，故可以按照货箱重量从大到小的顺序来装载。货箱重量从大到小的顺序来装载。例例4 装箱问题装箱问题 设有编号为设有编号为0、1、n-1

6、的的n种物品，体积分种物品，体积分别为别为v0、v1、vn-1。将这。将这n种物品装到容量都为种物品装到容量都为V的的若干箱子里。约定这若干箱子里。约定这n种物品的体积均不超过种物品的体积均不超过V，即对，即对于于0in，有，有0viV。不同的装箱方案所需要的箱子。不同的装箱方案所需要的箱子数目可能不同。数目可能不同。 装箱问题要求使装尽这装箱问题要求使装尽这n种物品的箱子数要少。种物品的箱子数要少。 样例：样例： V=1，n=8，物品的体积分别为：，物品的体积分别为：0.8，0.5， 0.4，0.4， 0.3，0.2， 0.2，0.2。 问题分析：问题分析：若考察将若考察将n种物品的集合分划

7、成种物品的集合分划成n个或小个或小于于n个物品的所有子集，最优解就可以找到。但所有个物品的所有子集，最优解就可以找到。但所有可能划分的总数可能划分的总数(枚举方法枚举方法)太大。对适当大的太大。对适当大的n，找出，找出所有可能的划分要花费的时间是无法承受的。所有可能的划分要花费的时间是无法承受的。能否下面这样贪心？为什么？能否下面这样贪心？为什么？ 先将先将n件物品按照体积从大到小排序，然后按排件物品按照体积从大到小排序，然后按排序结果依次将物品放到它第一个能放进去的箱子中。序结果依次将物品放到它第一个能放进去的箱子中。0.50.41、求图的最小生成树、求图

8、的最小生成树A B C D E F 2 2 1 3 1 5 4二、数据结构中的典型贪心算法二、数据结构中的典型贪心算法Prim 算法的贪心策略：算法的贪心策略：每次已连通部分与未每次已连通部分与未连通部分之间的最小边，直到图连通为止。连通部分之间的最小边，直到图连通为止。Kruskal 算法的贪心策略：算法的贪心策略：每次选择不构成回每次选择不构成回路的最小边，直到图连通为止。路的最小边，直到图连通为止。2、求图中顶点之间的最短路径、求图中顶点之间的最短路径A B C D E F 2 3 1 10 1 5 4贪心策略：贪心策略：无论是无论是Dijkstra还是还是Folyd算法都算法都是用已发

9、现的最短路径来替换。是用已发现的最短路径来替换。例如：例如：A到到B的最短路径的最短路径 1) 开始开始A到到B的最短路径为的最短路径为10, A到到D为为2 2) 在求出在求出A到到E的最短路径为的最短路径为3后，发现后，发现ADEB的长度为的长度为5，将，将A到到B的的10改为改为6。例例1 1：删数问题：删数问题三、例题分析：三、例题分析： 键盘输入一个高精度的正整数键盘输入一个高精度的正整数N N，去掉其中，去掉其中任意任意S S个数字后剩下的数字按左右次序组成一个个数字后剩下的数字按左右次序组成一个新的正整数。对给定的新的正整数。对给定的N N和和S S，寻找一种删数规，寻找一种删数

10、规则使得剩下得数字组成的新数最小。则使得剩下得数字组成的新数最小。 例如：例如：N=956742845689012N=956742845689012，S=3S=3时时 最小的结果为：最小的结果为：542845689012542845689012http:/ 这是一道运用贪心策略求解的典型问题。这是一道运用贪心策略求解的典型问题。此题所需处理的数据从表面上看是一个整数，此题所需处理的数据从表面上看是一个整数，通过对此题分析可以将所给出的高精度正整数通过对此题分析可以将所给出的高精度正整数看作由若干个数字所组成的一串字符，这是求看作由若干个数字所组成的一串字符，这是求解本题的一个重要手段。解本题的

11、一个重要手段。贪心策略：贪心策略： 如果前面的数字大于后面的数字，则应如果前面的数字大于后面的数字，则应该将此数字删除；直到删除该将此数字删除；直到删除s s个数为止。个数为止。例例2：部分背包问题：部分背包问题 从从n件不同价值、不同重量的物品中件不同价值、不同重量的物品中选取选取一部分一部分，在不超过规定重量的原则下，使该部，在不超过规定重量的原则下，使该部分价值最大。分价值最大。 贪心策略：贪心策略： 先计算每种物品单位重量的价值；用贪心先计算每种物品单位重量的价值；用贪心选择策略选择策略尽可能多的将单位重量价值高的物品尽可能多的将单位重量价值高的物品装入背包装入背包，如果这种物品全部装

12、入背包后，背，如果这种物品全部装入背包后，背包内物品的总重量未达到背包的容量，再选择包内物品的总重量未达到背包的容量，再选择次高的物品装入背包，依此下去次高的物品装入背包，依此下去。例例3：数列极差问题：数列极差问题 在黑板上写了在黑板上写了N个正整数作成的一个数列，个正整数作成的一个数列，进行如下操作：进行如下操作： 每一次擦去其中的两个数每一次擦去其中的两个数a和和b，然后在数，然后在数列中加入一个数列中加入一个数ab+1，如此下去直至黑板上，如此下去直至黑板上剩下一个数。剩下一个数。 在所有按这种操作方式最后得到的数中，在所有按这种操作方式最后得到的数中，最大的最大的max，最小的为，最

13、小的为min，则该数列的极差，则该数列的极差定义为定义为M=max-min。 任务：对于给定的数列，编程计算出极差任务：对于给定的数列，编程计算出极差M。 算法分析：算法分析： 1、求、求max与求与求min是两个相似的过程。下面是两个相似的过程。下面把求解把求解max与与min的过程分开，着重探讨求解的过程分开，着重探讨求解max的问题。的问题。 2、假设有、假设有3个数：个数：a、b和和max，并且假设它，并且假设它们存在关系：们存在关系：maxab，此时有三种求值方式，此时有三种求值方式，设其所求值分别为设其所求值分别为z1，z2，z3 则有则有: z1=(ab+1)max+1 z2=(

14、bmax+1)a+1 z3=(amax+1)b+1 因为因为: z1-z2=max-a=0，z1-z3= max-b=0 z2-z3=a-b=0即即: z1=z2=z3 贪心策略：贪心策略： 若使第若使第K (1KN-1) 次变换后所得值最大，次变换后所得值最大，必使第必使第k-1次变换后所得值最大。次变换后所得值最大。 在进行第在进行第K次变换时，只需取在进行次变换时，只需取在进行K-1次次变换后所得数列中的两最小数变换后所得数列中的两最小数p和和q施加操作：施加操作：ppq+1即可。即可。例例4 4：找零钱问题：找零钱问题 一个小孩买了价值少于一个小孩买了价值少于1 1美元的糖，并将美元的

15、糖，并将1 1美元的钱交给售货员。售货员希望用数目最少美元的钱交给售货员。售货员希望用数目最少数目硬币找给小孩。假设提供了面值为数目硬币找给小孩。假设提供了面值为2525美分、美分、1010美分、美分、5 5美分、及美分、及1 1美分的硬币。美分的硬币。贪心策略：贪心策略： 售货员分步骤组成要找的零钱数，每次加售货员分步骤组成要找的零钱数，每次加入一个硬币。每一次应选择使用小于等于零钱入一个硬币。每一次应选择使用小于等于零钱的最大价值的硬币。的最大价值的硬币。例例4 4：事件序列问题：事件序列问题 已知已知N N个事件的发生时刻和结束时刻。例如个事件的发生时刻和结束时刻。例如下表中的一些在时间

16、上没有重叠的事件，可以下表中的一些在时间上没有重叠的事件，可以构成一个事件序列，如事件构成一个事件序列，如事件22，8 8，1010。 事件序列包含的事件数目，称为该事件序事件序列包含的事件数目，称为该事件序列的长度。请找出一个最长的事件序列。列的长度。请找出一个最长的事件序列。问题分析问题分析2：如果在可能的事件如果在可能的事件a1a2an中中选取在时间上不重叠的最长序列，那么最长序选取在时间上不重叠的最长序列，那么最长序列中一定存在包含结束最早的事件。列中一定存在包含结束最早的事件。问题分析问题分析1： 不妨用不妨用Bi和和E i表示事件表示事件i的开始时刻和结的开始时刻和结束时刻。则题的要求就是找一个最长的序列：束时刻。则题的要求就是找一个最长的序列： a1a2an，满足：，满足： Ba1E a1=Ba2E a2= B an=M，那么显然用，那么显然用M条长度为条长度为1的线段的线段可以覆盖住所有的区间，所求的线段总长为可以覆盖住所有的区间，所求的线段总长为M。2、如果、如果N=1，那么显然所需线段总长为？，那么显然所需线段总长为？ 如果如果N=2，相当于，相当于N=1的情况下从某处断开的情况下从某处断开（从哪儿断开呢？）（从哪儿断开呢？） 如果如果N=k呢？呢？