# Ch14 貪婪演算法
> 搭配[green judge解題系統](http://www.tcgs.tc.edu.tw:1218/)
> Special thanks to [台中女中sagit老師](http://www.tcgs.tc.edu.tw/~sagit/index.htm) \<\(\_ \_\)\>
##
> 上一章：[排序](https://hackmd.io/s/ry9twDVpW)
> 下一章：[動態規劃](https://hackmd.io/s/ByZgGkLpW)
> 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)

## <font color='darkblue'>什麼叫貪婪</font>

貪婪演算法的原文是greedy
它的精神是
看到題目用最直覺、最短視近利的方法解決他

每次做決定都選當下最好的選擇
所有選擇合起來就會是整體最好的選擇

你可能會懷疑
這世界上有那種會因為短視近利而不好的問題嗎?

有的
請看看下方例子:

1.短視近利就好的例子
> 錢幣種類有5元、10元、50元、100元
> 輸入一個金錢總額
> 輸出使用最少錢幣的組合方法

這題目非常直覺
先看能夠用幾張100元，愈多愈好
剩下來的錢再看看能夠用幾個50元，愈多愈好
以此類推
很單純地從最大幣值的錢幣來換
就是最好的解答

2.短視近利會糟糕的例子
> 錢幣種類有1元、5元、10元、12元、16元、20元
> 輸入一個金錢總額
> 輸出最少錢幣的方法

假設要湊29元
如果依然從最大幣值的開始湊
那麼先拿了一個20元硬幣之後
剩的9元至少也要用一個5元和四個1元來湊
總共就會用掉6個硬幣
但是如果一開始不要拿20
改成一個5元、兩個12元
就可以只用3個硬幣了!!!

那該怎麼辦，只好試試所有可能的組合
再從裡面找最好的答案了
這個就放在下一章介紹

<font color='red'>至於這個單元介紹的所有題目都是可以短視近利貪婪地解決的</font>

能貪婪地解決當然簡單
但能夠分辨出遇到的題目能不能使用貪婪大法
以及該怎麼貪婪
則是這個單元的重頭戲

那麼先來做一道錢幣問題吧
> <font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Green Judge b034: 悠閒的超商店員 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b034)

## <font color='darkblue'>其他貪婪題目</font>

<font color='darkorange'>【例題】</font>
> 有一群人要上廁所
> 輸入總人數，以及每個人所需要的時間
> 希望讓大家總共的等待時間最小
> 請安排大家的順序
> 以及輸出所有人總共等了多久

各位應該都有共識
如果有好幾個人同時想要用廁所
大家會說「用最快的先去」
或是會毛遂自薦「我用很快，先讓我去」
因為如果讓用得久的先去
其他人就必須等他很久
但讓用得快的先去
其他人就只需要等他一下下

因此這題只要讓大家依照時間順序排好
並且對於每個人都去計算「排在他前面的所有人時間總合」
就會是它需要等待的時間
再把所有人的等待時間相加起來就是答案了

> <font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Green Judge b035: 超級保姆 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b035)

再看看下一題

<font color='darkorange'>【例題】</font>
> 你有好幾本書
> 希望把他們釘成一大本
> 所以你拿到書匠的店去
> 書匠的規則是一次只能把其中兩本釘在一起
> 而且收的錢是兩本書頁數的和
> (因為如果頁數和愈大，他就必須用愈大的釘子)
>
> 輸入你的書有幾本
> 以及每一本書原本有幾頁
> 請安排最適合的釘書順序
> 以及輸出最少需要付的錢

因為每次都是拿兩本書給書匠釘成一本
所以可以每次都很短視近利地拿最薄的兩本給他
當他釘完後
把新的書放進原書堆裡
再從裡面抓最薄的兩本出來給他釘
一直到所有書都被釘成同一本為止

例如像這樣
你有四本書
分別是2頁、3頁、4頁、7頁
一開始先拿2頁和3頁的釘起來，花費5元
於是你所有的書變成
5頁、4頁、7頁
這時再拿5和4釘起來，花費9元
變成9頁、7頁
最後再把9和7釘起來，花費16元
總共需要花費5+9+16=30元

30元絕對是最少的花費了
其他釘法一定不可能比30還要低

> <font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Green Judge b036: 史萊姆王 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b036)

## <font color='darkblue'>經典問題：最大連續元素和</font>

雖然他被歸類在動態規畫
但我認為他明明就是貪婪演算法...

題目是這樣的

<font color='darkorange'>【例題】</font>
> 老師的心情陰晴不定
> 有時候會幫你加分
> 有時候會把你扣分
> 因此為了避免被扣分
> 還是請假最好
> 但你又希望加分的時候可以來上課賺分數
>
> 而上課的規則是你只能來連續的一段時間
> 不能中間請假後來又跑來
>
> 已知老師每一天哪天會加多少分、哪天會扣多少分了
> 請安排一段時間連續來上課，並且可以得到最多分數
> 請輸出最多的分數

例如有6天
老師這六天的規則分別是
-1，+2，-1，+3，-5，+2
第一天把你扣一分
第二天幫你加兩分
第三天把你扣一分...以此類推

那麼最好的方法是來二到四天
也就是+2、-1、+3
總共可以淨賺4分，答案是4
這是最佳解了
不管改成什麼其他的組合
都只會讓答案更小而已

如果有4天
老師這四天的規則分別是
-1 -2 -1 -5
第一天扣一分
第二天扣兩分
第三天扣一分...以此類推

那嚇死人了
既然每天來都會被扣分，乾脆不來了!!
既然不來那就是賺到0分，答案是0

不過如果把所有起點終點的組合都試試看
又太麻煩了
這時又要借助貪婪的力量

這題可以這樣做：
從第一天開始往後累加
一邊累加一邊記得曾經出現過的最大累加值是多少
一旦累加的結果變成負值
就把累加歸零

例如剛才的例子，6天裡面分別是
-1 +2 -1 +3 -5 +2

從第一天開始
累加的值是-1
既然是-1，那當然不要拿最好
所以把第一天丟掉，累加的值歸0

接下來第二天是+2
所以累加的值是2，是目前出現過最大的值，紀錄一下

接下來第三天是-1
累加的值是1，雖然變小了有點糟，但後面可能出現更棒的
所以忍痛繼續加下去沒關係
但仍然記錄著，曾經出現過的最大值是2

接下來第四天是+3
累加的值變成4，太好了，把出現過的最大值改成4

接下來第五天是-5
累加的值變成-2
變成-2就太糟了，趕快把累加歸零，沒必要讓後面的結果承擔這個-2

接下來第六天是+2
累加的值變成2
但仍然記錄著，曾經出現過的最大值是4

因為曾經出現過最大的值是4
這題的答案就是4，也就是+2 -1 +3的這段和

> <font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Green Judge b026: 股海浮沈 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b026)

下一章是動態規劃
其中就會介紹到如果不能每次都短視近利
(例如最上面提到的最少硬幣組合)
必須比較所有可能的組合時
該怎麼有效率地解決

##
> 上一章：[排序](https://hackmd.io/s/ry9twDVpW)
> 下一章：[動態規劃](https://hackmd.io/s/ByZgGkLpW)
> 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)