(
课件网) 主题活动：贪心算法 赣科学技术版五年级下册 第5课 主题活动：贪心算法 (1)能用贪心算法解决教室调度问题。 (2)能用贪心算法解决背包问题。 任务卡 贪心算法又称贪婪算法，是一种重要的算法思想，在面对某些复杂问题的时候，贪心 算法可以帮助我们做出决策。贪心算法是在对问题求解时，总是做出在当前看来是最好 的选择，不从整体最优解上加以考虑，只做出某种意义上的局部最优解。 贪心算法的运用非常广泛，让我们从教室调度问题和背包问题入手，来学习它。 前言 一 教室调度问题 课程 开始时间 结束时间 美术 9:00 10.00 英语 9:30 10:30 数学 10:00 11:00 计算机 10.30 11:30 音乐 11:00 12:00 请说出你的想法 根据课程安排表将课程安排按照时间顺序呈现出来，如图所示 一 教室调度问题 请根据图思考具体做法。 具体做法： 步骤1:选出结束最早的课，它就是要在这间教室上的第一堂课。 步骤2:选择第一堂课结束后才开始的课。同样，要选择结束得最早的课，这将是要 在这间教室上的第二堂课。 步骤3:重复步骤1 和步骤2。 美术课结束得最早，为10:00,因此它就是第一堂课。接下来的课必须在10:00 后开 始，且结束得最早。英语课不行，因为它的时间与美术课冲突，数学课满足条件。最后计算机课与数学课的时间是冲突的，音乐课可以。具体见表 一 教室调度问题 因此根据表格,我们可以在这间教室上如下三堂课。 一 教室调度问题 课程 开始时间 结束时间 备注 美术 9:00 10:00 √ 英语 9:30 10:30 X 数学 10:00 11:00 √ 计算机 10:30 11:30 × 音乐 11:00 12:00 √ 二 背包问题 二 背包问题 背包可以装20千克的东西，音响最贵，先把它装进去，背包就没充足的空间装其他东西了。 请说出你的想法 二 背包问题 装了音响，价值为3000元。但是价值不是最高的，如果是装笔记本电脑和吉他，总价 值将为3500元。 在这里，贪心策略显然不能获得最优解，但是非常接近。 贪心算法 有时候，只需要找到一个能够大致解决问题的算法，此时贪心算法正好可以派上用场，因 为它们实现起来很容易，得到的结果又与正确结果相当接近。 请根据本次动手实践情况，在表5-3中相应的位置涂“”。(“非常好”涂 ,“好”涂,“还需努力”涂) 评一评 评价内容 自评 互评 教师评 理解贪心算法的含义 能用贪心算法解决教室调度问题 能用贪心算法解决背包问题 能说出贪心算法的优缺点 说一说贪心算法的优缺点 想一想贪心算法如何运用到生活中 练一练 谢谢聆听！ 谢谢 21世纪教育网（www.21cnjy.com) 中小学教育资源网站 兼职招聘： https://www.21cnjy.com/recruitment/home/admin ... ...
