若要用最簡單的方式去初步理解貪心法，其實就是
就好比現在有好多種蛋糕可以吃，但你的食量有限，最多也只能吃四、五塊蛋糕，那你要吃哪幾種蛋糕呢？當然是挑最好吃的那四、五種囉！更準確的來說，我們會在最一開始就先把最好吃的那塊蛋糕拿到盤子上、再把第二好吃的那塊蛋糕拿到盤子上……依此類推，也就是說，我們每次拿到盤子上的，都會是貪心地從當前還沒拿進來的蛋糕中拿取其中最好吃的那塊！
這種「每一步都選最好的」做法，我們就稱之為「貪心法」。
貪心法在資訊競賽出現得可多了，但多說無益，就直接讓大家看看貪心法會如何出現在資訊競賽中吧！
為了讓讀者熟悉一下「跟隨生活直覺的例子」，筆者在這邊準備了幾道題目作為範例。
有 $N$ 塊蛋糕，經過你審慎評估後，你了解到對於第 $i$ 塊蛋糕他的好吃度為 $y_i$。但無奈的是由於你食量有限，你只能吃下 $K$ 塊蛋糕。
試問在最佳策略下，若要最大化吃下的蛋糕好吃度總和，這個總和最大可以是多少？
這正是我們在最一開始用來介紹的基本貪心例題，照著我們提到的邏輯，那就是不斷地把好吃度最大的蛋糕吃掉，直到吃滿 $K$ 塊就行了！
但不對啊？如果執行 $K$ 次的找最大值，不就花了 $O(NK)$ 時間嗎？這樣在 $K$ 很大的時候可是會超時的！
這就是懂設計演算法重要的地方了，我們可以回到我們做法的本質──我們其實是在挑最好吃的那 $K$ 種來吃。
既然如此，這裡就該直接搬出我們的武器，也就是排序！只要做了一次排序後，最大的 $K$ 個數字必然就會被排在後面 $K$ 個位置，所以只要寫個迴圈把他們加總起來就好。這樣我們就能成功在 $O(N\log N)$ 時間內通過這題了！
順帶一提，這題是有辦法達到平均 $O(N)$ 的時間複雜度的……怎麼做呢？也許你會想複習看看基礎演算法 / 標準函式庫 ── <algorithm> 與 <numeric>……
有 $N$ 份作業，你知道每一份作業你都只需要花一小時就能寫完，但可怕的是，第 $i$ 份作業再過 $d_i$ 小時就要截止了！
想要讓所有作業在截止前完成可能還有些困難，因此，你希望能完成越多份作業越好。試問在最佳策略下，你能有幾份作業在截止時間前寫完？
*註：若一份作業一小時後截止，你有辦法馬上開始寫這份作業來趕上死線
這次來了一個全新的問題，我們一樣遵循著直覺──總是做死線最早的那份作業。
相信這也相當的合理，畢竟這些作業花的時間都一樣，那當然就是緊急程度越高的越要先做囉！又如果我們都已經盡全力在趕作業了，卻還是有作業來不及跟上死線，那就沒辦法了嘛。
一樣，拿出我們的排序直接對死線排下去，不過這次當然不是單純的算總合而已，我們還是得好好「模擬」這個寫作業的過程，好好紀錄自己已經花了多少時間，才可以確保下一份死線最早的作業是否已經過期。
有 $N$ 位客人來吃飯，其中第一個人的餐點需要煮 $C_i$ 分鐘，且他需要花 $E_i$ 分鐘才能吃完他的餐點。你身為餐廳老闆，你知道你的廚房同一時間只能煮一道料理，但每位客人都可以互相不干涉的享用自己的餐點，而一道料理煮完後便能馬上讓對應的客人開始吃，也就是說，當你在第 $t$ 分鐘開始煮第 $i$ 位客人的餐點，那麼這道餐點會在第 $t+C_i$ 分鐘後煮好，且這位客人一定會在第 $t+C_i+E_i$ 分鐘後享用完畢。
試求在最佳的烹飪順序下，最後一個人享用完他的餐點時間最早可以多早？
題目的參數開始變多了，但不怕，我們一樣試著遵循直覺來找到最佳的策略──那當然是先做需要被吃最久的那道。
不知道大家身邊是否總是有一位朋友的吃飯速度特別慢，每次一群人吃飯就得等他一個，如此想想好像就挺合理的，那當然是先做他的那道菜，才可以讓他有比較充足的時間吃飯囉。
這題的實作也是一樣，先排序之後好好「模擬」做菜的過程就好了，但可別忘了最終的答案是要針對每個人吃完的時間取 $\max$，畢竟就算我們最早就做了吃最慢的人點的菜，他還是有可能吃到大家都吃完了還在吃！
前面的例題看起來都非常的直覺，不過這樣隨性的講講就真的可以說是正確的嗎？實際在數學上，有很多論述都是需要更加嚴謹的，也有許多數學問題的答案常常違反我們的直覺（可參考三門問題、生日悖論）。讓我們來看看以下例題。
有 $N$ 個物品需要被堆在一個垂直的貨架上，已知第 $i$ 個物品的重量是 $w_i$，需要取用 $f_i$ 次，每次取用一個物品就需要將該物品上方的物品貨架升高才能做取用，因此取用一個物品消耗的能量為其上方的物品重量總和，而取用 $f_i$ 次就要花上 $f_i$ 倍的能量。
請問在最佳的物品擺放順序下，最小的能量消耗總和為何？
既然重量會被上方的物品影響，那還不簡單？把輕的擺上面就好啦……結果一測範例二由上到下排起來會是
$$
w_i = [3, 4, 5]\\
f_i = [1, 2, 3]
$$
就得到總能量消耗 $27$，居然錯了！
仔細試一下後，就會發現正確的排法應為
$$
w_i = [5, 4, 3]\\
f_i = [3, 2, 1]
$$
才可以真正得到最小的總能力消耗 $19$。
從上面的例子我們可以看到，不是遵循著直覺亂貪心一通就總是會對，就拿前面的「誰先晚餐」當例子，搞不好只是運氣好被我們瞎猜中結論而已！也因此，我們在下一個貪心的章節，會開始教大家如何掌握在一般貪心題目上判斷正確性的一些方法，來讓大家能對自己的「貪心策略」更加的自信。至於上面這題就一起留到下次再講吧！
貪心法看似簡單，但要深入的話是非常有學問的一個領域，我們會在往後的章節慢慢深入，敬請期待。
有 $N$ 份作業，你知道每一份作業你都只需要 $L$ 小時就能寫完，但可怕的是，第 $i$ 份作業再過 $d_i$ 小時就要截止了！
想要讓所有作業在截止前完成可能還有些困難，因此，你希望能完成越多份作業越好。試問在最佳策略下，你能有幾份作業在截止時間前寫完？
*註：若一份作業 $L$ 小時後截止，你有辦法馬上開始寫這份作業來趕上死線
現有 $n$ 本書需印刷裝訂。每一本書必須先印刷再裝訂。工廠有 $n$ 台裝訂機但只有一台印刷機。印刷機同時只能印一本書，而且必須印完一本書後才能印下一本書。現給定每一本書的印刷時間和裝訂時間，請計算所有書最快要多久才能印刷裝訂完畢。