《贪心算法ACM入门课件》由会员分享，可在线阅读，更多相关《贪心算法ACM入门课件（16页珍藏版）》请在金锄头文库上搜索。
1、贪心算法ACM入门经典,潘新武,什么是贪心算示,若在求解一个问题时，能根据每次所得到的局部最优解，推导出全局最优解或最优目标，那么，我们可以根据这个策略，每次得到局部最优解，进而逐步推导出问题的解，这种策略称为贪心法。,一个简单实例,例1：在n行m列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共n个数的和最大。 算法分析： 要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，我们可以设主出如下算法： 读入n,m，矩阵数据； total：=0； for i:=1 to n do begin 选择第i行最大的数，记为k； total:=total+k; end; 输出最大
2、总和total;,从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某个初始解出发，向给定的目标递推，但不同的是，推进每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即为贪心选择（在本例中这种贪心选择表现为选择一行中的最大整数）。这样，不断地将问题归纳为若干相似的子问题，最终产生出一个全局最优解。 特别应注意的是，局部贪心的选择是否可以得出全局最优解是能否采用贪心法的关键所在。对于能否使用贪心策略，应从理论上予以证明。,部分背包问题,给定一个最大容量为m的背包和n种食品，已知第i种食品最多有wi公斤，其价值为vi元/公斤，编程确定一个装货方案，使得装入背包中的所有食品的总价值最大
3、。 算法分析： 因为每一种食品都可以分割成单位块 ，显然，单位块的收益越大，所以它的局部最优满足全局最优，可以用贪习法解答。方法如下：先将单位块的收益按从大到小进行排列，然后用循环从单位块收益最大的开始取，直到不能取为止，便得到了最优解。,在解决上述问题的过程中，首先根据条件，找到贪心选择标准（vi），并依据这处标准直接逐步求得最优解。 一般来说，适用于贪心策略解题的问题具有以下特点： 1、可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步地进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且
4、每一个选择都仅做一次。 2、原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。,例：现有五件物品，重量分别为4、8、10、9、6.5公斤,它们的价值分别为12、21、24、17、10.5元。有一个背包，装入物品总量不得超过19公斤，该选哪几件物品放入背包内使总价值最大?,01背包问题,给定一个最大载重量为m的卡车n个物品。已知第I个物品的重量为wi，其最大价值为vi，设定m,wi,vi均为整数，编程确定一个装货方案，使得装入卡车中的所有物品的总价值最大，这些物品要么整个装入，要么不取，不能只取其中
5、的部分。,算法分析： 对于n个物品，要么被装，要么不装，也就是在满足卡车载重的条件下，如何选择物品，使得物品价值最大的问题。 从直观上来看，我们可以按照上例一样选择那些价值大而重量轻的物品，也就是可以按价值质量比（vi/wi）的大小来进行选择。可以看出。每做一次选择，都是从剩下的物品中选择那vi/wi最大的，这种局部最优的选择是否能满足全局最优呢？我们来看一个简单的例子： 设n=3，卡车最大载重量是100，物品a,b,c的重量分别是40,50,70，其对应的总价值分别为80，100，150。 情况A：按照上述思路，三个物品的vi/wi分别为：2，2，2.14。显然，我们首先选择物品c，得到价值
6、150，然后任意选择a或b，由于卡车最大载重量为100，因此卡车不能再装载其他的物品。 情况B：不按上述约束条件，直接选择a和b。可以得到价值为80+100=180，卡车装载的重量为40+50=90,没有超过卡车的实际载重，因此也是一种可行解。显然，这种解比上一种解要优化。问题出在什么地方呢？,空载10,载重90,价值180,情况B,从图中可以明显看出，情况A卡车的空载率比情况B要高。也就是说，上面的分析，只考虑了货物的价值质量比，而没有考虑卡车的运营效率，局部最优化，不能导致全局的最优化。因此，贪心法不能简单进行，而需要全面的考虑。并且最后得到证明。,排队打水问题,有n个人排队到r个水龙头打
7、水，他们装满水桶的时间分别是t1,t2,tn并且都是整数各不相同，应如何安排他们的打水顺序才能使他们花费的总时间最少？ 输入样例： 4 2 6 4 5 输出样例： 23,算法分析： 由于排队时，越靠前面的计算次数越多，因此越小的排在越前面得出的结果越小（可以用数学方法简单证明），所以这道题可以用贪心法解答。 1、将输入的时间按从小到大排序 2、将排序后的时间按顺序依次放入每个水龙头的队列中； 3、统计，输出答案。,参考程序： readln(n,r); fillchar(s,sizeof(s),0);初始化 j:=0;min:=0; for i:=1 to n do用贪心法求解 begin in
8、c(j); if j=r+1 then j:=1; sj:=sj+ai; min:=min+sj; end; writeln(min);,删数问题（NOIP94）,输入一个高精度的正整数n，去掉其中任意s个数字后的数按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。 输入新的正整数。（n不超过240位） 输入数据均不需判错。 输入格式 n s 输出格式 最后剩下的最小数 输入样例： 175438 4 输出样例 13,算法分析： 由于正整数n的有效数位为240位，所以很自然地采用字符串类型存贮n，那么如何决定哪S位被删除呢？是不是最大的S个数字呢？显然
9、不是，大家很容易举出一些反例。为了尽可能逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数递增，则删除最后一个数字；否则删除第一个递减区间的首字符，这样删一位便形成一个新数字串。然后回到串首，按上述规则再删下一个数字。重复以上过程s次为止，剩下的数字串便是问题的解了。 例如：n=175438 s=4 删数过程：15438（7），1438（5），138（4），13（8）,这样，删数问题就与如何寻找递减区间首字符这样一个简单问题对应起来了。不过还要注意一个细节性的问题，就是可能会出现字符串串首有若干个0的情况，甚至整个字符串都是0的情况。,参考程序框架 输入n,s; while s0 do begin i:=1; 从串首开始找 while (i1) and (n1=0) do delete(n,1,1);删去串首可能产生的无用0 writeln(n);,
