資源簡介

(共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

展開更多......

收起↑