信息学奥赛NOIP教程基于贪心的算法和应用ppt课件.ppt

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

1、基于贪心的算法和应用点击添加文本点击添加文本点击添加文本点击添加文本贪心算法引入【引例1】在n行m列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共n个数的和最大。【分析】要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。点击添加文本点击添加文本点击添加文本点击添加文本贪心算法引入【引例2】有1元、5元、10元、50元、100元、500元的硬币各C1、C5、C10、C50、C100、C500枚。现在要用这些硬币来支付A元，最少需要多少枚硬币？【分析】优先使用面值大的硬币。点击添加文本点击添加文本点击添加文本点击添加文本贪心算法定义贪心算法是从

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

3、容量是M＝150，有7个物品，物品可以分割成任意大小，要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。点击添加文本点击添加文本点击添加文本点击添加文本贪心算法的特点【分析】有以下几种策略可供选择：（1）每次挑选价值最大的物品装入背包，得到的结果是否最优？（2）每次挑选所占空间最小的物品装入是否能得到最优解？（3）每次选取单位容量价值最大的物品。点击添加文本点击添加文本点击添加文本点击添加文本贪心算法的特点解题一般步骤:1、设计数据找规律；2、进行贪心猜想；3、正确性证明（严格证明和一般证明）★一般证明：列举反例；★严格证明：数学归纳和反证法；4、程序实

4、现。点击添加文本点击添加文本点击添加文本点击添加文本经典例题※删数问题（NOI1995）※取数问题（IOI1996）※接水问题※最大整数※均分纸牌（NOIP2002）※三国游戏（NOIP2010）※火柴排队（NOIP2013）点击添加文本点击添加文本点击添加文本点击添加文本经典例题【例1】删数问题（NOI1994）键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。输出剩下的最小数。点击添加文本点击添加文本点击添加文本点击添加文本经典例题【分析】因为要删除S

5、个数字，可以一个一个地删，每一次删除的目的都是使剩下的数尽量小。那么在每一次删除时，应该选择哪个数字呢？最大的那个数字？还是最左边的那个数字？例如5768，删除7可以使剩余的数最小。//删除7会使后面的较小数前移，从而得到更小的数。如果不删除7，删除之前的较小数，会使大数7前移。删除7之后的较小数，则比删除7这个较大数得到的数要大。点击添加文本点击添加文本点击添加文本点击添加文本经典例题结论：每一次删除的数字应该是这个数字序列中最左边递减序列的第一个数字。具体操作为，按高位到低位的方向搜索递减区间。若不存在递减区间，则删除尾数字，否则删除递减区间的首数符，这样就

6、形成一个最小的数。重复上述规则，直到删除S个数字为止。点击添加文本点击添加文本点击添加文本点击添加文本经典例题例如：N＝8796542，S＝4第一次：N＝8796542，删除8；第二次：N＝796542，删除9；第三次：N＝76542，删除7；第四次：N＝6542，删除6，得到542。点击添加文本点击添加文本点击添加文本点击添加文本经典例题readln(n);readln(s);fork:=1tosdobegini:=1;while(i

7、gth(n)>1)and(n[1]=‘0’)dodelete(n,1,1)writeln(n);点击添加文本点击添加文本点击添加文本点击添加文本讨论一【例2】取数问题（IOI1996）给出2n（n≤100）个自然数（小于等于30000），将这2n个自然数排成一列，游戏双方A和B从中轮流取数，只允许从两端取数，A方先取，然后B方再取。取完时，谁取的数字总和最大为取胜方；若双方和相等，则B胜，试问A方是否有必胜策略？点击添加文本点击添加文本点击添加文本点击添加文本讨论一输入格式：两行，第一行一个整数n，第二行有2n个自然数。输出格式：只有一行，若A有必胜策略，则输出

8、“YES”，否则输出“N