,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,贪心策略,贪心策略,1,贪心方法的基本思想,贪心是一种解题策略，也是一种解题思想,使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优,利用贪心策略解题，需要解决两个问题：,该题是否适合于用贪心策略求解,如何选择贪心标准，以得到问题的最优/较优解,贪心方法的基本思想 贪心是一种解题策略，也是一种解题思想,2,引例,在N行M列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共N个数的和最大。,分析：要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，我们设计出如下算法:,读入N,M,矩阵数据；,Total:=0;,for I:=1 to N do begin对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;,repeat,if M=0 then Break;如果卡车满载则跳出循环,M:=M-Wi;,if M=0 then 将第I种商品全部装入卡车,else,将(M+Wi)重量的物品I装入卡车;,I:=I+1;选择下一种商品,until(M=N),算法问题初始化；读入数据,7,0,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）。,计算结果四舍五入至小数点后两位。,如果无法到达目的地，则输出“No Solution”。,样例：,Input,D1=275.6C=11.9D2=27.4 P=2.8 N=2,油站号I离出发点的距离Di每升汽油价格Pi1102.02.92220.02.2,Output,26.95（该数据表示最小费用）,例3 旅行家的预算 一个旅行家想驾驶汽车以最少的费用从一个城,12,分析：,需要考虑如下问题：,出发前汽车的油箱是空的，故汽车必须在起点（1号站）处加油。加多少油？,汽车行程到第几站开始加油，加多少油？,可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以归结为原问题的子问题。因此，原问题关键在于如何确定下一个加油站。通过分析，我们可以选择这样的贪心标准：,对于加油站I，下一个加油站J可能第一个是比油站I油价便宜的油站，若不能到达这样的油站，则至少需要到达下一个油站后，继续进行考虑。,对于第一种情况，则油箱需要（d（j）-d（i）/m加仑汽油。对于第二种情况，则需将油箱加满。,分析：需要考虑如下问题：,13,证明,设定如下变量：,Valuei：第i个加油站的油价；,Overi：在第i站时的剩油；,Wayi：起点到油站i的距离；,XI：X记录问题的最优解，XI记录油站I的实际加油量。,证明 设定如下变量：,14,证明,首先，X10，Over1=0。,假设第I站加的XI一直开到第K站。则有，XI.xk-1都为0，而XK0。,若ValueIValuek，则按贪心方案，第I站应加油为,T=（Wayk-WayI）/M-OverI。,若TXI,则预示着，汽车开到油站K，仍然有油剩余。假设剩余W加仑汽油，则须费用ValueI*W，如果W加仑汽油在油站K加，则须费用ValueK*W，显然ValueK*WValueI*W。,若ValueIValuek，则按贪心规则，须加油为,T=C-OverI（即加满油）。,若TXI，则表示在第I站的不加满油，而将一部分油留待第K站加，而ValueIValuek，所以这样费用更高。,证明首先，X10，Over1=0。,15,算法,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 汽车到达终点；,算法 I:=1 汽车出发设定为第1个加油站,16,例4,：d-规则问题,对任意给定的m(mN,+,)和n(nN,+,)，满足m1，使得K,aP，则修改P为：P=P-y|y=s,a,sN,+,，并称该d规则具有分值a。现要求编制一个程序，对输入的m,n值，构造相应的初始集合P，对P每应用一次d规则就累加其相应的分值，求能得到最大累加分值的d规则序列，输出每次使用d规则时的分值和集合p的变化过程。,例4：d-规则问题对任意给定的m(mN+)和n(nN+),17,基本思路,初看这一问题，很容易想到用贪心策略来求解，即选择集合中最大的可以删除的数开始删起，直到不能再删除为止，而且通过一些简单的例子来验证，这一贪心标准似乎也是正确的，例如，当m=2，n=10时，集合P2,3,10，运用上述“贪心标准”可以得到这一问题的正确的最优解d=54312，即其d-规则过程如下：,1.,a=5 P=2,3,4,6,7,8,9d=5,2.,a=4 P=2,3,6,7,9d=5+4=9,3.,a=3 p=2,7 d=5+4+3=12,基本思路初看这一问题，很容易想到用贪心策略来求解，即选择集合,18,分析,但是，如果再仔细地分析一个例子，当m=3，n18时，如果还是使用上述“贪心标准”，则得到问题的d-规则总分为d=35，其d-规则序列为（9,8,7,6,5），而实际上可以得到最大d-规则总分为d38，其对应的d-规则序列为（9,8,7,6,3,5）。,为什么会出现这样的反例呢？,这是因为，问题中要使得d-规则总分d值越大，不光是要求每一个d分值越大越好，也要求取得的d分值越多越好。,因此，本题不能采用上述的贪心策略,求解。,分析但是，如果再仔细地分析一个例子，当m=3，n18时，如,19,算法改进,将原算法基础上进行改进。下面给出新的算法：,建立集合P=m.n,从n div 2到m每数构造一个集合ci，包含该数在P中的所有倍数（不包括i本身）,从n div 2起找到第一个元素个数最少但又不为空的集合ci,在d分值中加上i,把i及ci集合从P集中删除，更新所有构造集合的元素,检查所有构造集合，若还有非空集合，则继续3步骤，否则打印、结束,算法改进将原算法基础上进行改进。下面给出新的算法：,20,贪心方法的应用,下面看m=3,n=18时的推演过程：,初始集合P=2.18 以及c9c3,找到i=9,ci=18,P=3.8,10.17,找到i=8,ci=16,P=3.7,10.15,17,找到i=7,ci=14,P=3.6,10.13,15,17,找到i=6,ci=12,P=3.5,10,11,13,15,17,找到i=3,ci=15,P=4,5,10,11,13,17,找到i=5,ci=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,每次把度最多的子结点与它的边切断。贪心策略1,25,反例1,反例1,26,贪心策略2,把后代最多的结与它的边切断。,贪心策略2把后代最多的结与它的边切断。,27,反例2,反例2,28,例1 小结,贪心策略1,贪心策略2,强剪枝,搜索,很完美,的算法,例1 小结贪心策略1贪心策略2强剪枝搜索很完美,29,问题讨论,下列问题,是否可以用贪心法解决此题？,问题讨论,30,讨论问题1,：,均分纸牌,例如 N=4，4 堆纸牌数分别为：98176移动3次可达到目的：从 取 4 张牌放到 （9 8 13 10）-从 取 3 张牌放