信息学奥赛NOIP贪心.ppt

1、贪心的算法和应用，点击添加文本，点击添加文本，点击添加文本，引入贪心的算法，引用1书架(noip-openjudge 4.6算法的贪心)John最近购买了存放奶牛养殖图书的书架，但书架很快就满了，只剩下顶面。John共有n头奶牛(1N20，000)，每头奶牛都有自己的高度Hi(1Hi10，000)，n头奶牛的总高度为s。书架高度为b (1bs2，000，007)。为了到达书架顶部，奶牛可以踩在其他母牛的背上，直到斯特罗汉的整个高度不低于书架的高度。当然，牛越多，危险就越大。为了帮助约翰到达书架的顶部，请寻找使用奶牛最少的解决方案。添加文本，单击添加文本，单击添加文本，单击添加文本，定义贪心算法

2、，贪心算法从问题的初始状态之一开始，期望通过逐步构建面向给定目标的最优解决方案的方法，创建全球最优解决方案。球表示当前状态。红色箭头指示目前的最佳决定。蓝色箭头表示其他决定。添加点击文本，添加点击文本，添加点击文本，添加点击文本，贪心算法的特征，选择贪心标准：选择贪心标准作为统一标准应用当前的“最高”标准，以此来应用原始问题，但切换到较小的子问题后，每个步骤似乎都是当前最好的选择。最佳子结构：如果某个问题的最佳解决方案包含该子问题的最佳解决方案，则该问题具有最佳子结构特性。点击添加文本，点击添加文本，点击添加文本，引入贪心算法，案例2金恩道(noip-openjudge 4.6算法的贪心)一天

3、，KID乘飞机去了有很多贵重金属的金恩岛。KID喜欢多种宝石的艺术品，但不拒绝这种珍贵的金属。但是他只有一个口袋，口袋最多只能装重量为w的物品。岛金属有不同重量的s种(n1，n2，ns)，并且每个金属的总价值也是v1、v2、vs。KID一次想拿走最有价值的金属，就问能拿走多少有价值的金属。注意金属可以任意分割，金属的价值与其重量成正比。点击添加文本，点击添加文本，点击添加文本，点击添加文本，贪心算法的功能，有几种策略可供选择。(1)每次选择价值最大的东西时，把东西放在背包里得到的结果是最佳的吗？(2)选择重量最小的东西时，能在装货地点得到最佳的解决方案吗？(？(3)每次选择单位重量值最大的项目

4、时。添加文本，单击添加文本，单击添加文本，单击添加文本，贪心算法的功能，故障排除一般步骤： 1，设计数据搜索规则；2、贪心的推测；3、准确证明(严格证明和一般证明)一般证明：列举反例；严格证明：数学刘涛和反证法；4、程序实施。单击添加文本，单击添加文本，单击添加文本，单击添加文本，实战案例，销售人员(NOIP2015入门级团队4号)电池寿命(渴望openjudge 4.6算法)，单击添加文本，单击添加文本，单击添加文本，实际战斗示例问题，实际战斗示例螺丝街是出口等于入口的死胡同，街的一边是墙，另一边是房东。螺丝街共n户，从I户到入口的距离是Si米。同一幢房子可以有多个家具，所以入口同一条街上可

5、以有多个家具。阿明从入口进来，依次向NASA的x家销售产品，然后再走原来的路。胺每走一米累计一分疲劳值，一户销售产品累计a分疲劳值。工作狂阿明想知道在不对其他x过度上路的情况下，能积累多少疲劳值。实际战斗示例，输入格式第一行有正整数n，表示螺钉距离家具的数量。下一行包含n个正整数。其中，第I个整数Si表示从假设I到入口的距离。数据保修S1S2Sn108。下一行包含n个正整数。其中，第I整数Ai表示向I家具销售产品时累积的疲劳值。数据保证Ai103。输出格式输出n行，每行有一个正整数，I行整数表示X=i时累积最大的疲劳值。实际战斗范例，输入范例1 5 1 2 3 4 2 3 4 5，输出范例1

6、15 19 22 24 25，s 1 2 3 4 5，a 1 2 3 4 5，开始，疲劳值3 6 9 12 15，实际战斗范例，输入范例1 5 1 2 3 4 1 2 a 1 2 3 4 5，开始，疲劳值1 2 3 4，实际战斗范例，输入范例15 1 2 3 4 1 2 3 4 5，输出范例1 15 19 22 24，s 1 2 3 4 5，A 1 2 3 4 5 输出范例1 15 19 22 24 25，s 1 2 3 4 5，a 1 2 3 4 5，开始，疲劳值1 2，实际战斗范例，输入范例1 5 1 2 3 4 1 2 3 4 5，输出范例1 15 19 22 24 25 输入范例25

7、1 2 4 5 4 5 4 3 4 1，输出范例2 12 17 21 24 27，疲劳值7 8，7 12 11，实际战斗范例，输入范例2 5 2 4 5 4 5 4 3 4 1，输出范例2 12 17 21 24 27，s 1 2，2 5 1 2 4 5 3 4 1，输出范例2 12 17 21 24 27，s 1 2，2 4 5，a 5 4，3 4 1，开始，疲劳值4，3，3，实际战斗范例，范例2输入5 1 2 4 输入范例25 1 2 4 5 4 4 3 4 1，输出范例2 12 17 21 27，s 1 2，2 4 5，5，5 4，3 4 1，开始，疲劳值3，加入按一下文字， 添加点击文

8、本，讨论，示例2电池寿命(noip-openjudge 4.6算法的贪心)小s购买了两个5号电池供电的手持游戏机。 为了长时间玩游戏，我买了很多5号电池，因为这些电池的质量因制造商而异，所以寿命不同，只能使用5小时或3小时。如果只有2个电池可以使用5小时1小时3小时，那么只能玩3小时游戏，其他1个电池不能使用，但是如果有3个电池可以使用3小时、3小时、5小时，那么用5小时可用的电池替换3小时、30分钟，其中1个就可以更好地利用。2小时30分钟后，用刚更换的电池更换剩下的一台电池(该电池还可用2.5小时)，这样就可以使用，不会浪费5.5小时。寻找目前已知的电池数量，以及电池可用的时间，以尽可能长

9、的方式使用。讨论，输入包含多个数据集。每个数据集由一个整数N (2N1000)表示电池数，N正整数表示电池使用时间。输出为每个数据集输出一行，表示电池可用的时间，保留到小数点后一位。示例输入2 3 5 3 5 5示例输出3.0 5.5，讨论，情况1:讨论，情况2:讨论，readln(n)；max 3360=-maxlongint；sum 3360=0；for I :=1 to n do begin read(x)；sum 3360=sum x；if xmax then max :=x；EndReadlnsum :=sum-max；if summax then writeln(sum max)/233603333001)else writeln(sum * 1.