程序设计培训讲义贪心算法优秀文档

程序设计培训之4：贪心算法袁辉勇2010年1月8日贪心法也称为贪婪法。

算法原理：以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪心法不要回溯。

算法优点：因为省去了为寻找解而穷尽所有可能所必须耗费的大量时间，因此算法效率高。

注意：通常使用贪心算法时需要证明。一、概述例1：找零钱问题。平时购物找钱时，为使找回的零钱的硬币数最少，不考虑找零钱的所有各种发表方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用贪心法。例2：在一个N×M的方格阵中，每一格子赋予一个数，规定每次移动时只能向上或向右。找出一条路径，使其从左下角至右上角所经过的权之和最大。a11a12a13a21a22a23a31a32a33a41a42a43分析：例如下面的一个2×3的方格阵中，每一格子都填写了一个数。3461210若按贪心法求解，路径为：1→3→4→6；若按动态规划法求解，路径为：1→2→10→6总结：由于贪心策略自身的特点，使得数字10所在的格子成为一个“坏格子”，即运用贪心策略找不到它，运用贪心策略求解的第一步（1→3）保证了局部最优解，却无法保证全局最优解。故本问题不能使用贪心法来求解。

例3最优装载问题有n个集装箱要装上1艘载重量分别为c的轮船，其中第i个集装箱的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。装载方案可能不唯一，约定长为n的01字符串(1:表示装)以字典序最大的那个为符合要求的装载方案。输出样例11010100输入样例：3504010405371030243540

枚举算法思路：

这个问题可以用枚举算法来解：设立一数组x，数组每个元素x[i]可能取值为0或1。如果x[i]为0，则货箱i将不被装上船；如果x[i]为1，则货箱i将被装上船。贪心算法思路：

这个问题也可以用贪心算法来解：由于货箱的大小都一样，但货箱的重量都各不相同，故可以按照货箱重量从大到小的顺序来装载。例4装箱问题设有编号为0、1、…、n-1的n种物品，体积分别为v0、v1、…、vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V，即对于0≤i＜n，有0＜vi≤V。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱子数要少。样例：V=1，n=8，物品的体积分别为：0.8，0.5，0.4，0.4，0.3，0.2，0.2，0.2。Kruskal算法的贪心策略：每次选择不构成回路的最小边，直到图连通为止。ABC231DEF不妨用B[i]和E[i]表示事件i的开始时刻和结束时刻。这就是在使用贪心法。贪心策略：按照事件的结束时间排序，每次选择开始时间大于等于上一个事件的结束时间的结束时间最早的事件。装箱问题要求使装尽这n种物品的箱子数要少。若使第K(1≤K≤N-1)次变换后所得值最大，必使第k-1次变换后所得值最大。这个问题可以用枚举算法来解：设立一数组x，数组每个元素x[i]可能取值为0或1。如果前面的数字大于后面的数字，则应该将此数字删除；1、求max与求min是两个相似的过程。将M个数排序，再计算相邻两个数的差，每次选择从差最大处断开。问题分析：若考察将n种物品的集合分划成n个或小于n个物品的所有子集，最优解就可以找到。但所有可能划分的总数(枚举方法)太大。对适当大的n，找出所有可能的划分要花费的时间是无法承受的。能否下面这样贪心？为什么？

先将n件物品按照体积从大到小排序，然后按排序结果依次将物品放到它第一个能放进去的箱子中。0.40.30.20.20.80.20.50.41、求图的最小生成树

ABCDEF2213154二、数据结构中的典型贪心算法Prim算法的贪心策略：每次已连通部分与未连通部分之间的最小边，直到图连通为止。Kruskal算法的贪心策略：每次选择不构成回路的最小边，直到图连通为止。2、求图中顶点之间的最短路径

ABCDEF23110154贪心策略：无论是Dijkstra还是Folyd算法都是用已发现的最短路径来替换。例如：A到B的最短路径1)开始A到B的最短路径为10,A到D为22)在求出A到E的最短路径为3后，发现ADEB的长度为5，将A到B的10改为6。例1：删数问题三、例题分析：键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按左右次序组成一个新的正整数。对给定的N和S，寻找一种删数规则使得剩下得数字组成的新数最小。例如：N=956742845689012，S=3时最小的结果为：542845689012算法分析：这是一道运用贪心策略求解的典型问题。此题所需处理的数据从表面上看是一个整数，通过对此题分析可以将所给出的高精度正整数看作由若干个数字所组成的一串字符，这是求解本题的一个重要手段。贪心策略：

如果前面的数字大于后面的数字，则应该将此数字删除；直到删除s个数为止。例2：部分背包问题

从n件不同价值、不同重量的物品中选取一部分，在不超过规定重量的原则下，使该部分价值最大。贪心策略：

先计算每种物品单位重量的价值；用贪心选择策略尽可能多的将单位重量价值高的物品装入背包，如果这种物品全部装入背包后，背包内物品的总重量未达到背包的容量，再选择次高的物品装入背包，依此下去……。例3：数列极差问题在黑板上写了N个正整数作成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数。在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。任务：对于给定的数列，编程计算出极差M。2、假设有3个数：a、b和max，并且假设它们存在关系：max>a>b，此时有三种求值方式，设其所求值分别为z1，z2，z31、求图的最小生成树如果N=2，相当于N=1的情况下从某处断开（从哪儿断开呢？）如果N=k呢？Kruskal算法的贪心策略：每次选择不构成回路的最小边，直到图连通为止。ABCDEFV=1，n=8，物品的体积分别为：0.ABC则题的要求就是找一个最长的序列：每一次应选择使用小于等于零钱的最大价值的硬币。在黑板上写了N个正整数作成的一个数列，进行如下操作：贪心策略：无论是Dijkstra还是Folyd算法都是用已发现的最短路径来替换。贪心法也称为贪婪法。不同的装箱方案所需要的箱子数目可能不同。1、求图的最小生成树假设提供了面值为25美分、10美分、5美分、及1美分的硬币。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。算法分析：1、求max与求min是两个相似的过程。下面把求解max与min的过程分开，着重探讨求解max的问题。2、假设有3个数：a、b和max，并且假设它们存在关系：max>a>b，此时有三种求值方式，设其所求值分别为z1，z2，z3则有: z1=(a×b+1)×max+1 z2=(b×max+1)×a+1 z3=(a×max+1)×b+1贪心策略：按照事件的结束时间排序，每次选择开始时间大于等于上一个事件的结束时间的结束时间最早的事件。二、数据结构中的典型贪心算法例如：A到B的最短路径ABCDEFKruskal算法的贪心策略：每次选择不构成回路的最小边，直到图连通为止。则有: z1=(a×b+1)×max+1Kruskal算法的贪心策略：每次选择不构成回路的最小边，直到图连通为止。V=1，n=8，物品的体积分别为：0.售货员希望用数目最少数目硬币找给小孩。DEF最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。设有编号为0、1、…、n-1的n种物品，体积分别为v0、v1、…、vn-1。如果前面的数字大于后面的数字，则应该将此数字删除；键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按左右次序组成一个新的正整数。因为:z1-z2=max-a>=0，z1-z3=max-b>=0z2-z3=a-b>=0即:z1>=z2>=z3贪心策略：若使第K(1≤K≤N-1)次变换后所得值最大，必使第k-1次变换后所得值最大。在进行第K次变换时，只需取在进行K-1次变换后所得数列中的两最小数p和q施加操作：p←p×q+1即可。例4：找零钱问题

一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少数目硬币找给小孩。假设提供了面值为25美分、10美分、5美分、及1美分的硬币。贪心策略：

售货员分步骤组成要找的零钱数，每次加入一个硬币。每一次应选择使用小于等于零钱的最大价值的硬币。例4：事件序列问题

已知N个事件的发生时刻和结束时刻。例如下表中的一些在时间上没有重叠的事件，可以构成一个事件序列，如事件{2，8，10}。事件序列包含的事件数目，称为该事件序列的长度。请找出一个最长的事件序列。事件编号01234567891011发生时刻13032564108155结束时刻347891081412181913问题分析2：如果在可能的事件a1<a2<…<an中选取在时间上不重叠的最长序列，那么最长序列中一定存在包含结束最早的事件。问题分析1：

不妨用B[i]和E[i]表示事件i的开始时刻和结束时刻。则题的要求就是找一个最长的序列：a1<a2<…<an，满足：B[a1]<E[a1]<=B[a2]<E[a2]<=…<=B[an]<E[an]贪心策略：按照事件的结束时间排序，每次选择开始时间大于等于上一个事件的结束时间的结束时间最早的事件。例5：区间覆盖问题用i来表示x轴上坐标为[i-1,i]的区间(长度为1)，并给出M个不同的整数，表示M个这样的区间。请你画几条线段覆盖住所有的区间，条件是：每条线段可以任意长，但是要求所画线段之和最小，并且线段的数目不超过N。例如：M=5时的整数1、3、4、8和11表示区间，要求所用线段不超过N=