重念一次早該補起來的「資料結構與演算法」。這篇筆記下動態規劃的貪婪演算法。
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/29906
本篇範圍：Chapter 10
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
貪婪演算法
1. 根據你現有的選擇，挑出最好的那一個，不過會忽略資料的整體結構。
2. 每一步僅考慮當下的情況，最好的決定是什麼
能解決的問題類型
1. Job Sequencing with Deadlines
先依照 Profit 來做由大到小排列，接著把工作優先放入符合的 Deadline 日期。如果沒有符合的日期可放，那就跳過。
2. Fractional Knapsack Problem – 分數背包問題
假設你有一個背包最多能裝 15 公斤，先算出每一單位物品單價，接著由高到低陸續裝入。請注意這個物品是可以用「分數」的型式裝入的，不一定要取用整個。
用 Greedy Method 找最短路徑，是有可能找到錯誤答案的。應該使用 Dijkstra’s 演算法
