基础算法6-贪心法1.ppt

引入： 若在求解一个问题时，能根据每次所得到的局部最优解，推导出全局最优或最优目标。那么，我们可以根据这个策略，每次得到局部最优解答，逐步而推导出问题，这种策略称为贪心法。 例如：在N行M列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共N个数的和最大。 分析：要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，我们设计出如下算法: 读入N, M,矩阵数据； Total := 0; For I := 1 to N do begin {对N行进行选择} 选择第I行最大的数,记为K； Total := Total + K； End； 输出最大总和Total； 从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标递推。但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相似的子问题，最终产生出一个全局最优解。 特别注意的是，局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键所在。对于能否使用贪心策略，应从理论上予以证明。 优点：一个正确的贪心算法拥有很多优点，比如思维复杂度低、代码量小、运行效率高、空间复杂度低等，是信息学竞赛中的一个有力武器。 缺点：集中表现在他的“非完美性”。通常我们很难找到一个简单可行并且保证正确的贪心思路，即使我们找到一个看上去很正确的贪心思路，也需要严格的正确性证明。这往往给我们直接使用贪心算法带来巨大的困难。 贪心２ 本题的另一解法在于突破现实生活中的思维惯性，认识到油箱中油的可更换性，每次我们都把油箱加满，并认为油箱中每次加的油是分离的，行驶的时候只使用其中最便宜的油，当遇到比油箱中便宜的油站的时候，把之前贵的油舍弃，补充上便宜的油，直到终点，将所有的油舍弃，记录下行驶过程中使用过油的价格便是最优解。 设定如下变量：?? Value[i]：第i个加油站的油价；?? Way[i]：起点到油站i的距离；? ?Over[i]：在第i站时的剩油；?? X[I]记录油站I的实际加油量 ?对于加油站I，下一个加油站J可能有2种情况：（1）比I的油贵；（2）比I的油便宜。?? (1)如果Value[j]Value[i]，则在第i个站需要加 x[i]:=(way[j]-way[i])/D2 -Over[i]升的油,使得油刚好能到j站；?? (2)如果Value[j]Value[i]，则在第i个站需要加加满油箱?x[i]:=c-Over[i]。 算法分析：L := C*D2； {油箱装满油能行驶的距离}repeat?? 在L距离以内，向后找第一个油价比I站便宜的加油站J；? if J存在 then???? ?? if I站剩余油能到达J then?????? ? ?? 计算到达J站的剩油?????? else??????? ? 在I站购买油，使汽车恰好能到达J站???else????? 在I站加满油；??I := J； {汽车到达J站}until 汽车到达终点； 按照这个框架把程序写出来 我们发现，上述△total恒大于0，所以也说明了任何次序的改变，都会导致等待时间的增加，从而证明了我们的设想。 这样，我们就得到了一种最优贪心策略：把接水时间少的人尽可能排在前面{其实，这一点是很明显的}。 这样一来，问题的本质就变成：把n个等待时间按非递减顺序排列，输出这种排列，并且求出这种排列下的平均等待时间。 【例4】活动安排 假设有一个需要使用某一资源的n个活动所组成的集合S，S={1,…,n}。该资源一次只能被一个活动所占用，每一个活动有一个开始时间bi和结束时间ei(bi=ei)。若bi=ej或bj=ei，则称活动i和活动j兼容。你的任务是：选择由互相兼容的活动所组成的最大集合。 输入： 输入文件名为act.in，共n+1行，其中第1行为n，第2行到第n+1行表示n个活动的开始时间和结束时间(中间用空格隔开)，格式为： n b1 e1 …… bn en 输出： 输出文件名为act.out，共两行，第1行为满足要求的活动占用的时间t，第2行为最大集合中的活动序号，每个数据之间用一个空格隔开。 样例输入： 11 3 5 1 4 12 14 8 12 0 6 8 11 6 　10 5 7 3 8