文档介绍：该【信息学奥赛NOIP教程基于贪心的算法和应用 】是由【非学无以广才】上传分享，文档一共【39】页，该文档可以免费在线阅读，需要了解更多关于【信息学奥赛NOIP教程基于贪心的算法和应用 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。基于贪心的算法和应用*信息学奥赛NOIP教程基于贪心的算法和应用*贪心算法引入【引例1】在n行m列的正整数矩阵中,要求从每行中选出1个数,使得选出的总共n个数的和最大。 【分析】要使总和最大,则每个数要尽可能大,自然应该选每行中最大的那个数。*信息学奥赛NOIP教程基于贪心的算法和应用*贪心算法引入【引例2】有1元、5元、10元、50元、100元、500元的硬币各C1、C5、C10、C50、C100、C500枚。现在要用这些硬币来支付A元,最少需要多少枚硬币? 【分析】优先使用面值大的硬币。*信息学奥赛NOIP教程基于贪心的算法和应用*贪心算法定义贪心算法是从问题的某一个初始状态出发,通过逐步构造最优解的方法向给定的目标前进,并期望通过这种方法产生出一个全局最优解的方法。 小球表示当前状态, 红箭头表示当前最优决策; 蓝箭头表示其他决策。方向*信息学奥赛NOIP教程基于贪心的算法和应用*贪心算法的特点贪心标准选择:所谓贪心标准选择就是应用当前“最好”的标准作为统一标准,将原问题变为一个相似的但规模更小的子问题,而后的每一步都是当前看似最佳的选择。 最优子结构:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。*信息学奥赛NOIP教程基于贪心的算法和应用*贪心算法的特点【引例3】部分背包问题 有一个背包,容量是M=150,有7个物品,物品可以分割成任意大小,要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。物品ABCDEFG体积35306050401025价值10403050354030*信息学奥赛NOIP教程基于贪心的算法和应用*贪心算法的特点【分析】 有以下几种策略可供选择: (1)每次挑选价值最大的物品装入背包,得到的结果是否最优? (2)每次挑选所占空间最小的物品装入是否能得到最优解? (3)每次选取单位容量价值最大的物品。*信息学奥赛NOIP教程基于贪心的算法和应用*贪心算法的特点解题一般步骤: 1、设计数据找规律; 2、进行贪心猜想; 3、正确性证明(严格证明和一般证明) ★一般证明:列举反例; ★严格证明:数学归纳和反证法; 4、程序实现。*信息学奥赛NOIP教程基于贪心的算法和应用*经典例题※删数问题(NOI1995)※取数问题(IOI1996)※接水问题※最大整数※均分纸牌(NOIP2002)※三国游戏(NOIP2010)※火柴排队(NOIP2013)*信息学奥赛NOIP教程基于贪心的算法和应用*经典例题【例1】删数问题(NOI1994) 键盘输入一个高精度的正整数N,去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S,寻找一种方案使得剩下的数字组成的新数最小。 输出剩下的最小数。*信息学奥赛NOIP教程基于贪心的算法和应用*