logo资料库

NOIP课件 - 动态规划算法详解.ppt

发布时间：2022-06-05 发布人：admin 分类：说明书 资料大小：0.18M 资料格式：ppt 举报 版权申诉
第1页 / 共46页
第2页 / 共46页
第3页 / 共46页
第4页 / 共46页
第5页 / 共46页
第6页 / 共46页
第7页 / 共46页
第8页 / 共46页
资料共46页，剩余部分请下载后查看
    优化，再优化！ ——从《鹰蛋》一题浅析对动态规划算法的优化 安徽省芜湖市第一中学 朱晨光
    引言 在当今的信息学竞赛中，动态规划可以说是 一种十分常用的算法。它以其高效性受到大家的 青睐。然而，动态规划算法有时也会遇到时间复 杂度过高的问题。因此，要想真正用好用活动态 规划，对于它的优化方法也是一定要掌握的。 本文将就《鹰蛋》这道题目做较为深入的分 析，并从中探讨优化动态规划的本质思想与一般 方法。
    问题 有一堆共M个鹰蛋，一位教授想研究这些 鹰蛋的坚硬度E。他是通过不断从一幢N层的楼 上向下扔鹰蛋来确定E的。 当鹰蛋从第E层楼及以下楼层落下时是不会 碎的，但从第（E+1）层楼及以上楼层向下落时 会摔碎。 如果鹰蛋未摔碎，还可以继续使用；但如 果鹰蛋全碎了却仍未确定E，这显然是一个失败 的实验。教授希望实验是成功的。
    问题 例如：若鹰蛋从第1层楼落下即摔碎，E=0； 若鹰蛋从第N层楼落下仍未碎，E=N。 这里假设所有的鹰蛋都具有相同的坚硬度。 给定鹰蛋个数M与楼层数N (M,N<=1000) , 求最 坏情况下确定E所需要的最少次数。 样例： M=1，N=10 ANS=10 （解释：只能将这个鹰蛋从下往上依次摔）
    算法一 由于是求最优值，我们自然想到了 使用动态规划！
    算法一 状态定义： f(i,j): 用i个蛋在j层楼上最坏情况下确定E 所需要的最少次数。 状态转移： i个鹰蛋 j层 i个鹰蛋 (j-w)层 f(i,j-w)次 (i-1)个鹰蛋 (w-1)层 f(i-1,w-1)次
    算法一 状态定义： f(i,j): 用i个蛋在j层楼上最坏情况下确定E 所需要的最少次数。 状态转移： f(i,j)=min{max{f(i-1,w-1),f(i,j-w)}+1|1<=w<=j}
    算法一 显然，这个算法的时间复杂度为O(N3) 太高了！ 如何才能降低它的时间复杂度呢？
    分享到：
    赞 收藏

    相关推荐

    资料库

    考试认证

    共收录20637份资料，累计11个分类，关注成员有19位，主要包括：真题,美赛,软考,PMP,Linux/Unix认证,思科认证,微软认证,Oracle认证,华为认证,软考等考,其它

    热门标签

    真题 美赛 软考 PMP Linux/Unix认证 思科认证 微软认证 Oracle认证 华为认证 软考等考 其它

    最新资料