信息学奥赛NOIP讲座基于贪心算法和应用课件.ppt

《信息学奥赛NOIP讲座基于贪心算法和应用课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于贪心的算法和应用点击添加文本点击添加文本点击添加文本点击添加文本贪心算法引入【引例1】书架（noip-openjudge4.6算法之贪心）John最近买了一个书架用来存放奶牛养殖书籍，但书架很快被存满了，只剩最顶层有空余。John共有N头奶牛(1≤N≤20,000)，每头奶牛有自己的高度Hi(1≤Hi≤10,000)，N头奶牛的总高度为S。书架高度为B(1≤B≤S<2,000,000,007).为了到达书架顶层，奶牛可以踩着其他奶牛的背，像叠罗汉一样，直到他们的总高度不低于书架高度。当然若奶牛越多则危险性越大。为了帮助John到达书架顶层，找出使用奶牛数目最少的解决方案吧。点击添加文

2、本点击添加文本点击添加文本点击添加文本贪心算法定义贪心算法是从问题的某一个初始状态出发，通过逐步构造最优解的方法向给定的目标前进，并期望通过这种方法产生出一个全局最优解的方法。小球表示当前状态；红箭头表示当前最优决策；蓝箭头表示其他决策。方向点击添加文本点击添加文本点击添加文本点击添加文本贪心算法的特点贪心标准选择：所谓贪心标准选择就是应用当前“最好”的标准作为统一标准，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前看似最佳的选择。最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。点击添加文本点击添加文本点击添加文本点击添加文本贪心算法引入

3、【引例2】金银岛（noip-openjudge4.6算法之贪心）某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为w的物品。岛上金属有s个种类,每种金属重量不同，分别为n1,n2,...,ns，同时每个种类的金属总的价值也不同，分别为v1,v2,...,vs。KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。点击添加文本点击添加文本点击添加文本点击添加文本贪心算法的特点【分析】有以下几种策略可供选择

4、：（1）每次挑选价值最大的物品装入背包，得到的结果是否最优？（2）每次挑选所占重量最小的物品装入是否能得到最优解？（3）每次选取单位重量价值最大的物品。点击添加文本点击添加文本点击添加文本点击添加文本贪心算法的特点解题一般步骤:1、设计数据找规律；2、进行贪心猜想；3、正确性证明（严格证明和一般证明）★一般证明：列举反例；★严格证明：数学归纳和反证法；4、程序实现。点击添加文本点击添加文本点击添加文本点击添加文本实战例题※推销员（NOIP2015普及组第4题）※电池的寿命（openjudge4.6算法之贪心）点击添加文本点击添加文本点击添加文本点击添加文本实战例题【例1】推销员（NOIP

5、2015普及组第4题）阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的X家住户推销产品，然后再原路走出去。阿明每走1米就会积累1点疲劳值，向第i家住户推销产品会积累A点疲劳值。阿明是工作狂，他想知道，对于不同的X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。实战例题【输入格式】第一行有一个正整数N，表示螺丝街住户的数量。接下来的一行有N个正整数，其中第i

6、个整数Si表示第i家住户到入口的距离。数据保证S1≤S2≤…≤Sn<108。接下来的一行有N个正整数，其中第i个整数Ai表示向第i户住户推销产品会积累的疲劳值。数据保证Ai<103。【输出格式】输出N行，每行一个正整数，第i行整数表示当X=i时，阿明最多积累的疲劳值。实战例题【输入样例1】51234512345【输出样例1】1519222425S12345A12345起点疲劳值3691215实战例题【输入样例1】51234512345【输出样例1】1519222425S12345A12345起点疲劳值1234实战例题【输入样例1】51234512345【输出样例1】1519222425S

7、12345A12345起点疲劳值123实战例题【输入样例1】51234512345【输出样例1】1519222425S12345A12345起点疲劳值12实战例题【输入样例1】51234512345【输出样例1】1519222425S12345A12345起点疲劳值1实战例题【输入样例2】51224554341【输出样例2】1217212427S12,245A54,341起点疲劳值78,71211实战例题【输入样例2】5122455