搜索
【引例1】书架（noip-openjudge4.6算法之贪心）John最近买了一个书架用来存放奶牛养殖书籍，但书架很快被存满了，只剩最顶层有空余。John共有N头奶牛(1≤N≤20,000)，每头奶牛有自己的高度Hi(1≤Hi≤10,000)，N头奶牛的总高度为S。书架高度为B(1≤B≤S2,000,000,007).为了到达书架顶层，奶牛可以踩着其他奶牛的背，像叠罗汉一样，直到他们的总高度不低于书架高度。当然若奶牛越多则危险性越大。为了帮助John到达书架顶层，找出使用奶牛数目最少的解决方案吧。贪心算法是从问题的某一个初始状态出发，通过逐步构造最优解的方法向给定的目标前进，并期望通过这种方法产生出一个全局最优解的方法。小球表示当前状态；红箭头表示当前最优决策；蓝箭头表示其他决策。方向贪心标准选择：所谓贪心标准选择就是应用当前“最好”的标准作为统一标准，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前看似最佳的选择。最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。【引例2】金银岛（noip-openjudge4.6算法之贪心）某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为w的物品。岛上金属有s个种类,每种金属重量不同，分别为n1,n2,...,ns，同时每个种类的金属总的价值也不同，分别为v1,v2,...,vs。KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。【分析】有以下几种策略可供选择：（1）每次挑选价值最大的物品装入背包，得到的结果是否最优？（2）每次挑选所占重量最小的物品装入是否能得到最优解？（3）每次选取单位重量价值最大的物品。解题一般步骤:1、设计数据找规律；2、进行贪心猜想；3、正确性证明（严格证明和一般证明）★一般证明：列举反例；★严格证明：数学归纳和反证法；4、程序实现。※推销员（NOIP2015普及组第4题）※电池的寿命（openjudge4.6算法之贪心）【例1】推销员（NOIP2015普及组第4题）阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的X家住户推销产品，然后再原路走出去。阿明每走1米就会积累1点疲劳值，向第i家住户推销产品会积累A点疲劳值。阿明是工作狂，他想知道，对于不同的X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。【输入格式】第一行有一个正整数N，表示螺丝街住户的数量。接下来的一行有N个正整数，其中第i个整数Si表示第i家住户到入口的距离。数据保证S1≤S2≤…≤Sn108。接下来的一行有N个正整数，其中第i个整数Ai表示向第i户住户推销产品会积累的疲劳值。数据保证Ai103。【输出格式】输出N行，每行一个正整数，第i行整数表示当X=i时，阿明最多积累的疲劳值。【输入样例1】51234512345【输出样例1】1519222425S12345A12345起点疲劳值3691215【输入样例1】51234512345【输出样例1】1519222425S12345A12345起点疲劳值1234【输入样例1】51234512345【输出样例1】1519222425S12345A12345起点疲劳值123【输入样例1】51234512345【输出样例1】1519222425S12345A12345起点疲劳值12【输入样例1】51234512345【输出样例1】1519222425S12345A12345起点疲劳值1【输入样例2】51224554341【输出样例2】1217212427S12,245A54,341起点疲劳值78,71211【输入样例2】51224554341【输出样例2】1217212427S12,245A54,341起点疲劳值54,33【输入样例2】51224554341【输出样例2】1217212427S12,245A54,341起点疲劳值4,33【输入样例2】51224554341【输出样例2】1217212427S12,245A54,341起点疲劳值33【输入样例2】51224554341【输出样例2】1217212427S12,245A54,341起点疲劳值3【分析】贪心：每次访问的位置＝max{max(已访问的最远位置的左边疲劳值),max(已访问的最远位置到某个位置距离*2+疲劳值)}起点已访问的最远位置疲劳值距离*2+疲劳值【例2】电池的寿命（noip-openjudge4.6算法之贪心）小S新买了一个掌上游戏机，这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏，他买了很多5号电池，这些电池的生产商不同，质量也有差异，因而使用寿命也有所不同，有的能使用5个小时，有的可能就只能使用3个小时。显然如果他只有两个电池一个能用5小时一个能用3小时，那么他只能玩3个小时的游戏，有一个电池剩下的电量无法使用，但是如果他有更多的电池，就可以更加充分地利用它们，比如他有三个电池分别能用3、3、5小时，他可以先使用两节能用3个小时的电池，使用半个小时后再把其中一个换成能使用5个小时的电池，两个半小时后再把剩下的一节电池换成刚才换下的电池（那个电池还能用2.5个小时），这样总共就可以使用5.5个小时，没有一点浪费。现在已知电池的数量和电池能够使用的时间，请你找一种方案使得使用时间尽可能的长。输入输入包含多组数据。每组数据包括两行，第一行是一个整数N(2≤N≤1000)，表示电池的数目，接下来一行是N个正整数表示电池能使用的时间。输出对每组数据输出一行，表示电池能使用的时间，保留到小数点后1位。样例输入2353335样例输出3.05.5情况一：情况二：readln(n);max:=-maxlongint;sum:=0;fori:=1tondobeginread(x);sum:=sum+x;ifxmaxthenmax:=x;end;readln;sum:=sum-max;ifsummaxthenwriteln((sum+max)/2:0:1)elsewriteln(sum*1.0:0:1);贪心算法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。特点是快，在运行过程中无回溯过程，每一步都是当前的最佳选择。难点是如何贪心和证明贪心的正确性，即如何用一个小规模的解构造更大规模的解。比赛过程中，需要胆大心细地归纳、分析。