# 貪心演算法
這個演算法會一直選擇對當前狀況最好的選擇直到結束，
聽起來很饒口，但換句話說，就是不斷執行現在"能夠選擇"、"看起來這個選擇最好"的選項，
之前用過的選項跟目前的選項沒有關係，只會以==眼前所看到的最好的判斷==去做決定，
可以想像的到，這種只挑目前最好的路的演算法，只要不能保證小部分的解是對的，則全域上就絕對不能以這種演算法執行下去。
制定貪心演算法只需幾個步驟
1. 想一個貪心的作法
2. 重複貪心直到程式的結束條件(該條件通常是明確的)
3. 把這個做法以小問題證明一遍(若是小問題的各種邊界條件皆能夠達成，則全域也應能達成)

而貪心演算法的條件大致有:
1. 問題能夠被分而治之
2. 子問題解的產生能夠推移到整體問題的解
3. 不用求出所有子問題的結果

## 使用貪心演算法的一些例子

### 0. bubble sort
bubble sort就是一個最簡單也能夠理解貪心的例子，我們每次都把最大的元素推向最後面，當然，這個序列就會變成一個降序排列，而每次都把最大的元素推向最後面，就是貪心的相信其他子序列做相同的事情，都會產生同樣的結果，而這就變成了子問題解決後->解決大問題

### 1. 排程問題
這個算是很經典的題目(? 在停偉學長要我們買的書中也有提到
有n件工作。各工作分別從時間 s~i~ 開始，以時間 t~i~ 結束，做任何工作都得全程參與，做工作的時間線不能重疊，最多能夠參加多少工作?

策略:從可以選擇的工作中不斷選擇結束時間最早的工作

而可行性呢?
我的想法是只要不斷選擇結束時間最早的工作，那麼剩餘的時間理所當然也會是最多的，所以每一次的選擇都是在為後面的工作挪出最大的時間區間，而最大的時間區間本身就是說明"之後也能選最多項工作"，由於我們只需要算出最多能選幾次，不在乎選出的工作有多少種可能，例如:

====== 工作一
===== 工作二
==== 工作三
###### (=代表工作區間)
以上述例子而言，不管先選的是工作一或工作二，之後接續的工作都應該是工作三，不過對本題來說都無所謂，選的都應該是工作一，因為我們要的只是選擇工作後產生的最大剩餘時間，也就是貪心的選擇最大剩餘子區間。
f(i~r~)代表i~r~的結束時間，
證明:有兩個A,O set，A代表greedy algorithm找出來的解，O代表另一個最佳解，A的集合有{i~1~,i~2~,...i~k~} O是j，先假設他們兩個工作個數一樣，則f(i~r~)<=f(j~r~)，示意:
請看右下角的i跟j，如果f(i~r~)>f(j~r~)，則greegy應該選j~r~才對，所以此情況不合理。
而若|O|=|A|+1，則j~r+1~應該也能被我們的greegy選才對，因為j~k+1~一定在j~k~後面，而f(i~k~)<=f(j~k~)，我們的greedy應該能夠選到才對，矛盾很明顯。

圖片來源:[https://www.youtube.com/watch?v=hZjp35QI-40&list=PLj6E8qlqmkFtoRpLn6IXnH_eboef-3QvZ&index=10&ab_channel=NYCUOCW](https://)
### 2.背包問題the knapsack
w~n~是目前重量，n會從0~W，w[i]是項目重量
盜賊有個能夠承受重量W的袋子，有數個不同價值與重量的東西，這些東西無法被分割，必須在有效時間之前算出最好的總價值並不讓袋子爆炸，ok，這其實是一個要用動態規劃做的題目，但是我認為要解決這個題目的遞迴式也很貪心，每次選擇物品時，只要考慮這東西的重量是否能夠裝進袋子，以及裝進袋子時，這個東西會不會比沒裝時更有價值而已，袋子選擇項目的話，要考慮w~n~-w[i]時的最大價值加上這個項目的價值，以及w[i]時的價值
:::info
v(w[i])代表w~i~的價值
max( v(w~n~),v( w~n~-w[i])+v(w[i]) )
:::
所以價值只在選w~i~時決定，並且只看選項目時剩下的重量最大的價值，也就是每個重量，都貪心的看選完w~i~之後有沒有比較大，並且每個重量都是'最大價值'，所以子項目->下一個子項目也是'最大價值'，這trivial的解釋了為什麼這個方式能行。
範例程式:[https://web.ntnu.edu.tw/~algo/KnapsackProblem.html](https://)
(這其實不符合貪心是不看後照鏡的，但我覺得這也很貪心嘛)

### 3.uva714
有n個人，跟m本書，每本書可以有不同頁數，叫這些人抄書，並且抄書時不能是第1,4,5書這樣抄，只能抄連續序列的書像是2,3,4，抄最多的人要盡量能抄少就抄少，要怎麼做?
我們用二分找出'最大的頁數'，比起列出所有子序列所擁有的最大，我們設一個假設的最大的頁數m，如果這個m找出的人超出所需要的人，就把二分的minimum改為m+1，並進行下一次二分(因為太小所以找出的人太多)，反之就把maximum改成m，直到maximum<minimum為止.
這題用到了貪心的搜尋盡量小的最大頁數，並使用二分搜尋來達到這個結果。
(其實我只是看別人怎麼寫才知道怎麼解釋這題)
https://github.com/Diusrex/UVA-Solutions/blob/master/714%20Copying%20Books.cpp

---

> 推薦別人的筆記
https://hackmd.io/@CLKO/rkhigGlTG?type=view

---
### 使用貪心的優點
1. 先把問題以貪心的想法出發，應該很快就能知道這個方法行不行得通，舉個反例就知道問題可不可以就這麼解決
2. 就算行不通，也能從反例知道問題的難點在哪
3. 通常執行速度很快
---
### 缺點
1. 有時候會不知道怎麼證明
2. 貪心是用來短視近利的，不適合解決很多很多問題