贪心策略课件

贪心策略贪心策略1贪心方法的基本思想

贪心是一种解题策略，也是一种解题思想使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优利用贪心策略解题，需要解决两个问题：该题是否适合于用贪心策略求解如何选择贪心标准，以得到问题的最优/较优解贪心方法的基本思想贪心是一种解题策略，也是一种解题思想2引例 在N行M列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共N个数的和最大。

分析：要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，我们设计出如下算法:读入N,M,矩阵数据；Total:=0;forI:=1toNdobegin {对N行进行选择}选择第I行最大的数,记为K；Total:=Total+K；end；输出最大总和Total；引例 在N行M列的正整数矩阵中，要求从每行中选出1个数，使得3贪心策略求解的问题具有的特点：可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。但并不是所有具有最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法——动态规划（例如“0-1背包问题”与“部分背包问题”）贪心策略求解的问题具有的特点：可通过局部的贪心选择来达到问题4例1部分背包问题给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。例1部分背包问题给定一个最大载重量为M的卡车和N种食品，有5分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然6算法问题初始化； {读入数据}按Vi从大到小将商品排序；I:=1;repeatifM=0thenBreak; {如果卡车满载则跳出循环}M:=M-Wi;ifM>=0then将第I种商品全部装入卡车else将(M+Wi)重量的物品I装入卡车;I:=I+1; {选择下一种商品}until(M<=0)OR(I>=N)算法问题初始化； {读入数据}70,1背包问题给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。0,1背包问题给定一个最大载重量为M的卡车和N种动物。已知第8算法?按贪心法,有反例.设N=3，卡车最大载重量是100，三种动物A、B、C的重量分别是40，50，70，其对应的总价值分别是80、100、150。算法?按贪心法,有反例.9例2排队打水问题有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少？例2排队打水问题有N个人排队到R个水龙头去打水，他们装满水10分析由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，这里就不再赘述），所以这道题可以用贪心法解答，基本步骤：将输入的时间按从小到大排序；将排序后的时间按顺序依次放入每个水龙头的队列中；统计，输出答案。分析由于排队时，越靠前面的计算的次数越多，显然越小的排在越前11例3旅行家的预算一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱时空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途加油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……，N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“NoSolution”。样例：InputD1=275.6 C=11.9 D2=27.4 P=2.8 N=2油站号I离出发点的距离Di每升汽油价格Pi1102.02.92220.02.2Output26.95（该数据表示最小费用）例3旅行家的预算一个旅行家想驾驶汽车以最少的费用从一个城12分析：需要考虑如下问题：出发前汽车的油箱是空的，故汽车必须在起点（1号站）处加油。加多少油？汽车行程到第几站开始加油，加多少油？可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以归结为原问题的子问题。因此，原问题关键在于如何确定下一个加油站。通过分析，我们可以选择这样的贪心标准：对于加油站I，下一个加油站J可能第一个是比油站I油价便宜的油站，若不能到达这样的油站，则至少需要到达下一个油站后，继续进行考虑。对于第一种情况，则油箱需要（d（j）-d（i））/m加仑汽油。对于第二种情况，则需将油箱加满。分析：需要考虑如下问题：13证明设定如下变量：Value[i]：第i个加油站的油价；Over[i]：在第i站时的剩油；Way[i]：起点到油站i的距离；X[I]：X记录问题的最优解，X[I]记录油站I的实际加油量。证明设定如下变量：14证明首先，X[1]≠0，Over[1]=0。假设第I站加的X[I]一直开到第K站。则有，X[I]..x[k-1]都为0，而X[K]≠0。若Value[I]>Value[k]，则按贪心方案，第I站应加油为T=（Way[k]-Way[I]）/M-Over[I]。若T<X[I]，则汽车无法从起点到达第k个加油站；与假设矛盾。若T>X[I],则预示着，汽车开到油站K，仍然有油剩余。假设剩余W加仑汽油，则须费用Value[I]*W，如果W加仑汽油在油站K加，则须费用Value[K]*W，显然Value[K]*W<Value[I]*W。若Value[I]<Value[k]，则按贪心规则，须加油为T=C-Over[I] （即加满油）。若T<X[I]，则表示在第I站的加油量会超过汽车的实际载油量，显然是不可能的。若T>X[I]，则表示在第I站的不加满油，而将一部分油留待第K站加，而Value[I]<Value[k]，所以这样费用更高。证明首先，X[1]≠0，Over[1]=0。15算法I:=1{汽车出发设定为第1个加油站}L:=C*D2；{油箱装满油能行驶的距离}repeat在L距离以内，向后找第一个油价比I站便宜的加油站J；ifJ存在thenifI站剩余油能到达Jthen计算到达J站的剩油else在I站购买油，使汽车恰好能到达J站 else在I站加满油；I:=J； {汽车到达J站}until汽车到达终点；算法I:=1{汽车出发设定为第1个加油站}16例4：d-规则问题对任意给定的m(m∈N+)和n(n∈N+)，满足m<n，构造一初始集合：P={x|m≤x≤n,x∈N+}(m,n≤100)现定义一种d规则如下：若存在a∈P，且存在K∈N+,K>1，使得K

a∈P，则修改P为：P=P-{y|y=s

a,s∈N+}

，并称该d规则具有分值a。现要求编制一个程序，对输入的m,n值，构造相应的初始集合P，对P每应用一次d规则就累加其相应的分值，求能得到最大累加分值的d规则序列，输出每次使用d规则时的分值和集合p的变化过程。例4：d-规则问题对任意给定的m(m∈N+)和n(n∈N+)17基本思路初看这一问题，很容易想到用贪心策略来求解，即选择集合中最大的可以删除的数开始删起，直到不能再删除为止，而且通过一些简单的例子来验证，这一贪心标准似乎也是正确的，例如，当m=2，n=10时，集合P＝{2,3,…,10}，运用上述“贪心标准”可以得到这一问题的正确的最优解d=5＋4＋3＝12，即其d-规则过程如下：1.a=5P={2,3,4,6,7,8,9} d=52.a=4P={2,3,6,7,9} d=5+4=93.a=3p={2,7} d=5+4+3=12基本思路初看这一问题，很容易想到用贪心策略来求解，即选择集合18分析但是，如果再仔细地分析一个例子，当m=3，n＝18时，如果还是使用上述“贪心标准”，则得到问题的d-规则总分为d=35，其d-规则序列为（9,8,7,6,5），而实际上可以得到最大d-规则总分为d＝38，其对应的d-规则序列为（9,8,7,6,3,5）。为什么会出现这样的反例呢？这是因为，问题中要使得d-规则总分d值越大，不光是要求每一个d分值越大越好，也要求取得的d分值越多越好。因此，本题不能采用上述的贪心策略求解。分析但是，如果再仔细地分析一个例子，当m=3，n＝18时，如19算法改进将原算法基础上进行改进。下面给出新的算法：建立集合P={m..n}从ndiv2到m每数构造一个集合c[i]，包含该数在P中的所有倍数（不包括i本身）从ndiv2起找到第一个元素个数最少但又不为空的集合c[i]在d分值中加上i把i及c[i]集合从P集中删除，更新所有构造集合的元素检查所有构造集合，若还有非空集合，则继续3步骤，否则打印、结束算法改进将原算法基础上进行改进。下面给出新的算法：20贪心方法的应用下面看m=3,n=18时的推演过程：初始集合P={2..18}以及c[9]~c[3]找到i=9,c[i]={18},P={3..8,10..17}找到i=8,c[i]={16},P={3..7,10..15,17}找到i=7,c[i]={14},P={3..6,10..13,15,17}找到i=6,c[i]={12},P={3..5,10,11,13,15,17}找到i=3,c[i]={15},P={4,5,10,11,13,17}找到i=5,c[i]={10},P={4,11,13,17}到此所有构造集合全部为空，d=9+8+7+6+3+5=38贪心方法的应用下面看m=3,n=18时的推演过程：21贪心方法的应用讨论：能否证明此贪心策略是正确的？能否找到其他更好的算法？贪心方法的应用22例5传染病控制

染病的传播具有两种很特殊的性质：第一是它的传播途径是树型的，一个人X只可能被某个特定的人Y感染，只要Y不得病，或者是XY之间的传播途径被切断，则X就不会得病。第二是，这种疾病的传播有周期性，在一个疾病传播周期之内，传染病将只会感染一代患者，而不会再传播给下一代。这些性质大大减轻了蓬莱国疾病防控的压力，并且他们已经得到了国内部分易感人群的潜在传播途径图（一棵树）。但是，麻烦还没有结束。由于蓬莱国疾控中心人手不够，同时也缺乏强大的技术，以致他们在一个疾病传播周期内，只能设法切断一条传播途径，而没有被控制的传播途径就会引起更多的易感人群被感染（也就是与当前已经被感染的人有传播途径相连，且连接途径没有被切断的人群）。当不可能有健康人被感染时，疾病就中止传播。所以，蓬莱国疾控中心要制定出一个切断传播途径的顺序，以使尽量少的人被感染。 你的程序要针对给定的树，找出合适的切断顺序。例5传染病控制 染病的传播具有两种很特殊的性质：23人传播途径模型人传播途径模型24每次把度最多的子结点与它的边切断。

贪心策略1每次把度最多的子结点与它的边切断。贪心策略125……反例1……反例126贪心策略2把后代最多的结与它的边切断。

贪心策略2把后代最多的结与它的边切断。27反例2反例228例1小结贪心策略1贪心策略2强剪枝搜索很完美的算法例1小结贪心策略1贪心策略2强剪枝搜索很完美29问题讨论下列问题 是否可以用贪心法解决此题？问题讨论30讨论问题1：均分纸牌例如N=4，4堆纸牌数分别为：

①9②8③17④6

移动3次可达到目的：

从③取4张牌放到④（981310）->从③取3张牌放到②（9111010）->从②取1张牌放到①（10101010）。[输入]：

键盘输入文件名。文件格式：

N（N堆纸牌，1<=N<=100）

A1A2…An（N堆纸牌，每堆纸牌初始数，l<=Ai<=10000）[输出]：

输出至屏幕。格式为：

所有堆均达到相等时的最少移动次数。讨论问题1：均分纸牌例如N=4，4堆纸牌数分别为：

31输入：498176

输出：3设list为纸牌序列，其中list[i]为第i堆纸牌的张数（1≤i≤n），ave为均分后每堆纸牌的张数，即；ans为最少移动次数。我们采用“移动一次使得一堆牌数达到平均值”的贪心策略：由左而右的顺序移动纸牌。若第i堆纸牌的张数list[i]超出平均值，则移动一次(ans+1)，将超出部分留给下一堆，既第i+1堆纸牌的张数增加list[i]-ave；若第i堆纸牌的张数list[i]少于平均值，则移动一次(ans+1)，由下一堆补充不足部分，既第i+1堆纸牌的张数减少ave-list[i]；右邻堆取的牌输入：输出：设list为纸牌序列，其中list[i]为第i堆32问题是，在从第i+1堆中取出纸牌补充第i堆的过程中，可能会出现第i+1堆的纸牌数小于零(list[i+1]-(ave-list[i])<0)的情况，这时可以理解为一个“先出后进”的栈。由于纸牌的总数是n的倍数，因此后面的堆会补充第i+1堆ave-list[i]-list[i+1]+ave张纸牌，使其达到均分的要求。第四堆补充第三堆第三堆补充第二堆第二堆补充第一堆在枚举分牌方案时，是否可以利用上述计数方法呢？问题是，在从第i+1堆中取出纸牌补充第i堆的过程中，可能会出33讨论问题2:删数问题键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按左右次序组成一个新的正整数。对给定的N和S，寻找一种删数规则使得剩下得数字组成的新数最小。讨论问题2:删数问题键盘输入一个高精度的正整数N，去掉其中任34删数问题

键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。

输出应包括所去掉的数字的位置和组成的新的正整数。(N不超过240位)

输入数据均不需判错。

删数问题键盘输入一个高精度的正整数N，去掉其中任意S35试题中正整数N的有效位数为240位，必须采用可含256个字符的字串来替代整数。贪心选择:使用尽可能逼尽目标的方法来逐一删去其中S个数符,每一步总是选择一个使剩下的数最小的数符删去。具体：按高位→低位的方向搜索递减区间。若不存在递减区间，则删尾数符；否则删递减区间的首字符，这样形成了一个新数串。然后回到串首，重复上述规则，删下一数符……依此类推，直至删除S个数符为止。例如:N='178543',S=4,删数过程如下:

↓N='178543'

↓

'17543'

↓

'1543'

↓

'143''13'

试题中正整数N的有效位数为240位，必须采用可含256个36write(‘N=’);readln(N);{输入数串}write(‘S=’);readln(S);{输入应删的数字个数}whileS>0dobegin{逐一删去S个数符}i:=1;while(i<length(N))and(N[i]<=N[i+1])doinc(i);{搜索递减区间}delete(N,i,1);{删去该区间的首数符}dec(S);end;{while}while(length(N)>1)and(N[1]=‘0’)dodelete(N,1,1);{删去串头的无用零}writeln(N);{输出剩下的数码}write(‘N=’);readln(N);{输入数串37讨论问题3:数列极差问题在黑板上写了N个正整数作成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。

编程任务：对于给定的数列，编程计算出极差M.讨论问题3:数列极差问题在黑板上写了N个正整数作成的一个数38任务调度问题

一个单位时间任务是个作业,如要在计算机上运行一个程序,它恰覆盖一个单位的运行时间.给定一个单位时间任务的集合S,对S的一个调度即S的一个排列,其中规定了这些任务的执行顺序.该调度中的第一个任务开始于时间0,结束于时1;第二个任务开始于时间1,结束于时间2,……单处理器上具有期限和罚款的单位时间任务调度问题的输入如下:1.包含n个单位时间任务的集合S=1,2,……,n;2.n个取整的期限d1,……,dn,(1≤d,≤n),任务i要求在di前完成;3.n个非负的权(或罚款)w1,……,wn.如果任务i没在时间di之前结束,则导致罚款wi;要求找出S的一个调度,使之最小化总的罚款.任务调度问题

一个单位时间任务是个作业,如要在计算机上运行一39概念迟任务──调度中在规定期限后完成的任务，试题要求迟任务的罚款总和最小化;早任务──调度中在规定期限前完成的任务，早任务的罚款总和最大化对应问题的解概念40两个贪心1、按照罚款的单调递减顺序来安排各个子任务，使得早任务的罚款总和最大化2、在时序上保证指定任务尽早完成。实现方式：⑴.按期限递增的顺序对早任务进行调度。即只要在调度中有两个分别完成于时间K和K+1的早任务i、j且dj<di，我们就互换i和j的位置，使得任务i在交换后仍然是早的，而任务j被移到更前的位置;⑵.如果某个早任务X跟在迟任务Y之后，我们可以交换X和Y的位置，使得早任务先于迟任务;某一调度中早任务的集合构成了一个独立的任务集A，因为A中任务按期限单调递增的顺序进行调度后，没有一个任务是迟的，且A中期限为ｔ或更早的任务个数小于等于ｔ。设目前早任务个数为num,早任务集合中期限小于等于num的任务个数为t。若t<di，则当前第i个任务作为早任务插入第num+1个空位。

两个贪心1、按照罚款的单调递减顺序来安排各个子任务，使41最初，我们设所有n个时间空位都是空的。然后按罚款的单调递减顺序(任务1，任务2，任务3，任务4，任务5，任务6，任务7)来考虑各个子任务。在考虑任务j时，如果有一个恰处于或前于dj的时间空位仍空着，则将任务j赋与最近的这样的空位，并填入;如果不存在这样的空位，则将任务j赋与一个还未被占的、最近的空位。按上述贪心策略选择了任务1，2，3，4，7，放弃任务5，6。最终的最优调度为〈2，3，4，1，7，5，6〉，任务ｉ1234567期限dｉ4243146罚款wｉ70605040302010最初，我们设所有n个时间空位都是空的。然后按罚款的单调递42设N─任务个数,num─目前早任务个数;t─罚款总和list─任务序列。其中list[i].k、list[i].d、list[i].w为任务I的编号,期限和罚款。list[i].k<0,则任务i为早任务;list[i].k>0,则任务i为迟任务;lt─辅助数组Pck为早任务的编号序列；算法如下：读入任务数N;Fori:=1toNDoBegin,读入任务i的期限List[i].d和罚款List[i].w;List[i].k:=I{记下其序号}End;{for}list序列按罚款单调递减的顺序排序；