资源简介

(共17张PPT)
主题活动：贪心算法
赣科学技术版五年级下册
第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

展开更多......

收起↑