# 貪心 Greedy ## 3/15社課 --- ## 貪心(貪婪)演算法 ##### 不太像演算法的演算法 ##### 其實應該排在dp前 ---- ### 什麼是貪心 就是取 "在當下最佳的情況" ---- ### 舉例 如果要從數字裡取兩個數字和最大 就取最大(佳)的兩個數 (8，10)  ---- ### 缺點 取當下最佳的情況 不一定是所有選擇中最好的 ---- 如果一開始取最短的(3) 反而總和是最長距離  --- ## 範例 ---- 如果有n份工作，他們有各自的期限 每份工作都要在期限內完成 在不考慮完成工作需要的時間下 先從最接近期限的工作開始排列 ---- 在ABCDEF中 選擇最有價值的物品放入背包 每樣物品都可以拆分 請讓背包價值最大(背包有重量限制)  ---- 為了讓背包價值最大 先從最貴的物品開始放入 其次是第二高、第三高... 就能達成條件 ---- ~~實際上當然不會有這種簡單題目~~ [其他背包問題(dp)](https://web.ntnu.edu.tw/~algo/KnapsackProblem.html) ---- ### [最大連續元素和](https://zerojudge.tw/ShowProblem?problemid=d784) ---- 從數列一開始直接往後疊加 取記錄到的最大值 如果疊加到負數就歸零 重新記錄 ---- ### [史萊姆王](http://35.72.96.204/ShowProblem?problemid=b036) ---- 每次拿最廢的兩隻史萊姆進行合體 所耗能量最小 最後加總起來就會最小 --- ### 怎麼確定貪心法是不是最好的解法? ---- 方案1:提出比目前方案更好的B方案 (顯然不太實際) ---- 方案2:假設B方案才是最好方案 並使用矛盾法證明此方案不存在 ---- - 法1:對於任意某個解B1 都提出相異解B2比B1好 - 法2:證明原本方法比方案B好 ---- 詳細證明可以看資芽這篇 [p.10](https://sprout.tw/algo2023/ppt_pdf/week05/greedy.pdf) --- 練習:[i792](https://zerojudge.tw/ShowProblem?problemid=i792) 謝謝你 造橋人，我的超人