freepascal 贪心算法.ppt

LOGO 贪心算法 在现实生活中，我们经常会下意识地作出贪心的选择 ，例如在商场购买商品时总是寻求物美价廉的策略，在质量一样的情况下，价格低的商品经常被列为首选。 贪心的思想在程序设计中也很实用。在竞赛中经常会遇到一类求解最优解的问题，而且在解决这一类问题时，需要我们逐步地选择一个最优的子目标，最后递推的得到问题的全局最优解。下面我们先来看个引例。 引例： 例1、购买贺年卡（card.pas） 【问题描述】 新年快到了，笑笑打算给他的好朋友们发贺年卡，而且他已经选好了自己要购买的贺卡的样式。俗话说得好，货比三家，笑笑来到了商店，看了各个商铺这种贺卡的价钱。不仅如此，笑笑还记住了每个商铺的存货量。已知笑笑打算购买m张贺卡，问他最少花多少钱。 输入格式： 第一行有两个正整数m和n。其中m表示要购买贺年卡的数量，n表示商铺的个数 以下n行，每行有两个整数，分别表示该商铺这种贺年卡的单价和存货量。 输出格式： 仅一个数，表示笑笑所花的最少钱数 【输入样例】： 10 4 4 3 6 2 8 10 3 6 【输出样例】： 36 数据规模： 0m，n≤1000 可以保证最后的结果在长整形范围内，商铺的总存货量不少于m 【问题分析】 这是一个十分简单而又非常实际的问题。 可以将贺卡按照单价由低到高排序，然后从便宜的买起，直到达到规定的数量。这就体现了“通过求子问题的最优解得到整体最优”的思想 程序样例：课本标程 For i:=1 to n-1 do for j:=i+1 to n do if data[i,0]data[j,0] then begin t:=data[i,0]; data[i,0]:=data[j,0]; data[j,0]:=t; t:=data[i,1]; data[i,1]:=data[j,1]; data[j,1]:=t; end; 一、贪心策略 贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出的最优解（或较优解）的一种解题方法，即： 从问题的某一个初始解出发，向给定的目标推进（递推），推进的每一步都做一个当前看起来最佳的贪心选择，不断将问题实例归纳为更小的相似的子问题，并期望通过所做的局部最优选择产生出一个全局最优解。这就是贪心的思想。 贪心策略并不是从整体上加以考虑，它所作出的选择只是在某种意义上的局部局部最优解。当然，许多问题自身的特性决定了该题运用贪心策略可以得到最优解惑较优解。 二、适用于贪心算法来求解的问题要具有如下特点： 1、要有贪心选择性（即同一规则）： 所谓贪心选择性是指应用同一规则，将原问题变为一个相似的、但规模更小的子问题，而后的每一步都是做当前看似最佳的选择，这种选择依赖于已作出的选择，但不依赖于未作出的选择。 从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程，因此贪心法有较高的时间效率。 2、要有最优子结构性质： 所谓最优子结构性质是指原问题的最优解包含了其子问题的最优解。 下面来看几个例题： 例2、删数问题（shanshu.pas） 【问题描述】 键盘输入一个正整数n，去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小（n不超过240位）。 【输入】 两行，第一行：正整数n，第二行：正整数s 【输出】 n去掉s个数字后组成的新的最小的正整数m 【样例输入】 123006 2 【样例输出】 1006 通过上面的样例可以发现：删数的过程中每一步总是选择一个使剩下的数最小的数字删去，也即每一步都做当前看来的最优选择。如何选择呢？ 为了保证删一个数字后得到的数最小，总是按照从高位到低位的顺序有哪些信誉好的足球投注网站不下降区间（数字一直不变小的区间），找到后删除不下降区间的末尾数字，这样得到了一个新数串。然后回到串首，重复上述规则，删下一个数字……依次类推，直至删除s个数字为止。 总之，每一次删除的一个数字都是从首位开始的最长连续不下降序列的最末位数字。 下面结合本例题对本课件第9张幻灯片中贪心思想做进一步的解释： 1、贪心选择性 本题中设正整数n有m位，第一步删除一个数字使剩下的m-1位数字最小，把问题变成从m-1位的整数中去掉s-1个数字后的新数最小的子问题。第二步再选择一个使剩下的新数最小的数字删去，又把问题归纳为在m-2位正整数中去掉s-2个数字后的新数