信奥_贪心算法基础

1、贪心算法QQ:培训信奥新昌浙江贪心算法 需要勇气和智慧的算法NOIP 基础算法 培训浙江 新昌信奥培训 QQ:贪心算法例1 最简单的贪心：找零钱找零钱方法就是一种贪心算法贪心策略：先找大额的例如：找80元， 找50， 余30再找20， 余10再找10， 余0 共计3 张零钞在现有币值的情况下，上述算法显然是对的。问题：假如有40元币值的呢？上述算法正确的条件是什么？贪心算法概念v贪心算法是：指从问题的初始状态出发，向给定的目标递推, 通过若干次当时最佳的贪心选择而得出最优值(或较优解)的一种解题方法。其实，从“贪心算法”一词我们便可以看出，贪心算法总是作出在当前看来是最优的选择，也就是说贪心算

2、法并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解（是否是全局最优，需要证明） 。 q贪心算法是一种思想，不是简单的算法。贪心算法贪心策略的特点贪心算法有什么样的特点呢？我认为，适用于贪心算法解决的问题应具有以下2个特点： 1、贪心选择性质：o所谓贪心选择性质是指应用同一规则同一规则，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。2、局部最优解：o由于运用贪心策略

3、解题在每一次都取得了最优解，但能够保证局部最优解的不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，但贪心策略比动态规划时间效率更高且占用内存更少，编写程序更简单。 贪心算法贪心算法的基本步骤贪心算法的基本步骤 1、从问题的某个初始解出发。2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模，最终覆盖全部范围或规模。3、将所有部分解综合起来，得到问题的最终解。贪心算法通常包括排序过程，这是因为贪心选择的对象通常是一个数值递增或递减的有序关系贪心算法贪心算法的典型应用贪心算法的典型应用部分背包问题：先按价值/重量比进行排序，优先装

4、入价值/重量比大的物体。单源最短路径：求从源到所有其他各顶点的最短路长度（Dijkstra算法）。最小生成树（Prim算法和Kruskal算法）。贪心算法例2 背包问题问题：问题：已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为wi。假定将物品i的一部分xi放入背包就会得到pixi的价值，这里，0 xi1，pi0。如果这些物品重量的和大于M，要求所有选中要装入背包的物品总重量不得超过M，而装入背包物品获得的总价值最大。即,max1iniixpMxwinii1 0 xi1，pi0，wi0，1in 满足约束条件的任一集合(x1，xn)是一个可行解(即能装下)，使目标函数取最大值的可行解是

5、最优解。贪心算法例子n3，M=20，P(25，24，15) W (18，15，10)。其中的四个可行解是： (x1，x2，x3)wixi pixi (1/2，1/3，1/4) 165 2425(1，2/15，0) 20 282(0，2/3，1) 20 31(0，1，1/2) 20 315 在这四个可行解中，第个解的总价值最大。这个解是背包问题在这一情况下的最优解。贪心算法贪心策略与最优量度表价值作为量度标准 这是最容易想到的，即每装入一件物品就使背包获得最大可能的价值增量。在这种量度标准下的贪心方法就是按价值的非增次序将物品一件件放到背包中去。如果正在考虑中的物品放不进去，则可只取其一部分来装

6、满背包。第个解就是这种量度标准下的贪心方法所产生的解，显然它不是最优的。原因在于背包可用容量消耗过快。容量作为量度 让背包容量尽可能慢地被消耗。这就要求按物品重量的非降次序来把物品放人背包。例3.1的解就是使用这种贪心策略得到的，它仍不是最优解。其原因在于容量虽然慢慢地被消耗，但价值没能迅速地增加。价值/重量 为量度 即每一次装入的物品应使它占用的每一单位容量获得当前最大的单位价值。这就需使物品的装人次序按pi/wi比值的非增次序来考虑。解就是使用这种贪心策略得到的，它是最优解。贪心算法部分背包问题的贪心算法procedure knapsack(p，w，m，x，n) / p(1.n)和w(1.

7、n)分别n件物品的价值和重量 / m是背包的容量大小 x(1.n)是解 排序 :按p(i)/w(i) 从大到小排序的 fillchar(x,sizeof(x),0); /将解向量初始化为零/ cu:=m; /cu是背包剩余容量/ for i:=1 to n do begin if w(i)cu then break ; x(i) :=1; cu:=cu-w(i); end; if in then x(i) :=cu/ w(i);end ; /greedy-knapsack贪心算法例3 射击竞赛射击竞赛题目描述题目描述 射击的目标是一个由R*C(2RC1000)个小方格组成的矩形网格。每一列恰有

8、2 2个个白色的小方格和R-R-2 2个个黑色的小方格。行从顶至底编号为1-R，列从左至右编号为1-C。射击者可射击C次。在连续的C次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。如果存在正确的射击方法，则要求找到它。输入输入输入第一行为R，C，后面R行每行C个数，如果为0则为白格，1则为黑格输出输出输出正确方案, 每行两个数即射击坐标，否则输出-1 贪心算法射击竞赛射击竞赛 贪心策略：先打白格最少的行先打白格最少的行 （类似拓扑排序）1 统计所有行包含的白格数2 从还没有射击格的行中选出一个白格数最少的3 检查所选的行1) 若所选行的白格数为0

9、，则输出无解；2) 否则从所选行的白格中任选一个作为射击格，并将与该格同列的另一个白格所处行的白格数减14 返回到第2步，直到所有的行都有射击格。5 若还有列没有选射击格，则在该列任选一白格作为射击格即可贪心算法例4 活动安排问题活动安排序列问题序列问题已知N个事件的发生时刻和结束时刻（见下表，表中事件已按结束时刻升序排序）。一些在时间上没有重叠的事件，可以构成一个事件序列，如事件 2，8，10。 事件序列包含的事件数目，称为该事件序列的长度。请编程找出一个最长的事件序列。事件编号01234567891011发生时刻130325641081515结束时刻3478910121415181920贪

10、心算法例4 算法分析：算法分析：不妨用Begini和Endi表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1a2an，满足：Begina1Enda1= BeginanEndan可以证明，如果在可能的事件可以证明，如果在可能的事件a1a2a1a2anan中选取在时间上不重叠的中选取在时间上不重叠的最长序列，那么一定存在一个包含最长序列，那么一定存在一个包含a1a1（结（结束最早）的最长序列。束最早）的最长序列。贪心算法例4 活动安排问题 我们将输入的活动以其完成时间的作非减序排列，每次总是选择具有最早完成时间的活动作为选择的活动。直观上，按这种方法选择相容活动为未安排活动留下

11、尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。 算法复杂度：O(n)：mb:=E1; /B: Begin E: End f: truefor i:=2 to n do if fi then if (Bimb) then fi:=false else mb:=Ei;ans:=0for i:=1 to n do inc(ans,ord(fi);贪心算法例4 活动安排问题 若被检查的活动i的开始时间Bi小于最近选择的活动j的结束时间Ei，则不选择活动i，否则选择活动i加入到选择集合中。 贪心算法并不总能求得问题的整体最优解整体最优解。但对于

12、活动安排问题，却总能求得的整体最优解。这个结论可以用数学归纳法证明。贪心算法例例5 哈夫曼编码哈夫曼编码哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。 例如一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。定长变码需要300,000位，而按表中变长编码方案，文件的总码长为： （451+133+123+163+94+54）1000=224,000。比用定长码方案总码长较

13、少约45%。 贪心算法v对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。 v编码的前缀性质可以使译码方法非常简单。 v表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。 v平均码长定义为： v使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。v哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。 贪心算法哈夫曼编码 （ NOIP2004TG-2 合并果子）将最小的E F加入树，频率和为14将最小的B C加入树，频率和为25将最小的 D EF加入树，频率和为30将最小的 25 3

14、0加入树，频率和为55将最小的 A 55加入树，频率和为100 (编程实现：堆排序)将小的写在左边，大的写在右边，形成一颗树：哈弗曼树。每条边按左边为0，右边为1，就是哈夫曼编码贪心算法例6 旅行家的预算问题一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市，给定两个城市间的距离d1，汽车油箱的容量是c，每升汽油能行驶的距离d2，出发时每升汽油的价格是p，沿途加油站数为n（可为0），油站i离出发点的距离是di，每升汽油的价格是pi。 计算结果四舍五入保留小数点后两位，若无法到达目的地输出“No answer 若输入： d1=275.6 c=11.9 d2=27.4 p=8 n=2 d1=1

15、02 p1=2.9 d2=220 p2=2.2 输出26.95 贪心算法例例6 旅行家的预算问题加油总该找便宜的油站加，没办法时再贵也只好加了。只要算到终点就行了（旅行家只旅行，不去玩的）因此，我们的策略是：找下一个现在加满能到达的价格比现在便宜的油站，根据距离确定加满或加到刚好到该站。如果现在加满，到不了任何站，无解。u设现在的油站的油价为 P0,现在加满能到达的最便宜的油站的油价为 Pi, u如果P0=Pi ,加到刚好到该站当然，我们设终点的油价为0 （最最便宜了）贪心算法例例6 例程var d1,c,d2,p8, maxl,mincost :double; d,p :array0.100

16、0 of double; n :longint; ok :boolean; procedure init;var i:longint;begin read(d1,c,d2,p8,n); maxl:=d2*c; /加满油能开的最大距离 d0:=0; p0:=p8; /始点 dn+1:=d1; pn+1:=0; /终点 for i:=1 to n do read(di,pi); ok:=true; mincost:=0;end;Procedure doit;.procedure print;begin if ok then writeln(mincost:0:2)else writeln(No S

17、olution);end;begininit; doit; print; end.贪心算法procedure doit;var i,nowp,minp_i,maxl_i :longint; minp,remainoil :double;begin nowp :=0; / 当前位置 remainoil:=0; /汽油余量 while nowp= n do begin i:=nowp+1; maxl_i:=nowp; minp:=pnowp; minp_i:=nowp; while (di-dnowp=maxl) and (i=n+1) do begin maxl_i:=i; / 最远点 if p

18、iminp then begin minp:=pi; minp_i :=i; break; end; inc(i); end;例例6 例程 核心部分 if maxl_i=nowp then /无解 begin ok:=false; exit; end; if minp_inowp then begin /开到油价比现在低的站 mincost:=mincost+pnowp*( (dminp_i-dnowp)/d2-remainoil); nowp:=i; remainoil:=0; end else begin /开到最远的站 mincost:=mincost+pnowp*( c-remaino

19、il); remainoil:=c-(dmaxl_i-dnowp)/d2; nowp:=maxl_i; end; end;end;贪心算法例例7 任务调度问题任务调度问题 一个单位时间任务是个作业,如要在计算机上运行一个程序,它恰覆盖一个单位的运行时间。给定一个单位时间任务的集合S,对S的一个调度即S的一个排列,其中规定了这些任务的执行顺序。该调度中的第一个任务开始于时间0,结束于时1;第二个任务开始于时间1, 结束于时间2;。 单处理器上具有期限和罚款的单位时间任务调度问题的输入如下: 1.包含n个单位时间任务的集合S=1,2,n; 2.n个取整的期限d1,dn,(1d,n),任务i要求在d

20、i前完成; 3.n个非负的权(或罚款)w1,wn。如果任务i没在时间di之前结束, 则导致罚款wi; 要求找出S的一个调度,使之最小化总的罚款。贪心算法例例7 算法分析算法分析: 这个问题首先我们定义两个概念:迟任务调度中在规定期限后完成的任务，试题要求解出最小化迟任务的罚款总和;早任务调度中在规定期限前完成的任务，最大化早任务的罚 款总和正好对应问题的解;任意一个调度可通过下述方式安排成规范形式: 1.按期限递增的顺序对早任务进行调度。即只要在调度中有两个分别完成于时间K和K+1的早任务i、j且djdi，我们就互换i和j的位置，使得任务i在交换后仍然是早的，而任务j被移到更前的位置; 2.如

21、果某个早任务X跟在迟任务Y之后，我们可以交换X和Y的位置，使得早任务先于迟任务; 任一调度中早任务的集合构成了一个独立的任务集A，因为A中任务按期限单调递增的顺序进行调度后，没有一个任务是迟的、且A中期限为t或更早的任务个数小于等于t。显然A集合为满足传递性质的独立子集,而问题的解为其中罚款总和最大的一个子集。贪心算法例例7 算法分析算法分析: 例如: 任务i 1 2 3 4 5 6 7 期限di 4 2 4 3 1 4 6 罚款wi 70 60 50 40 30 20 10 最初，我们设所有n个时间空位都是空的。然后按罚款的单调递减顺序(任务1，任务2，任务3，任务4，任务5，任务6，任务7

22、)对各个子任务作贪心选择。在考虑任务j时，如果有一个恰处于或前于dj的时间空位仍空着，则将任务j 赋与最近的这样的空位，并填入; 如果不存在这样的空位，则将任务j赋与一个还未被占的、最近的空位。 按上述贪心策略选择了任务1，2，3，4，7，放弃任务5，6。最终的最优调度为2，4，3，1，7，5，6，其总的罚款为W5+W650。贪心算法例例7 例程例程program tasks_with_limit_and_fine;const maxn = 500; type node = record k, d, w : integer;end;var n, i, j, num, t : integer; list : array 1.maxn of node; pck : array 1.ma