HackMDCh14 貪婪演算法
搭配green judge解題系統
Special thanks to 台中女中sagit老師 <(_ _)>
上一章：排序
下一章：動態規劃
回目錄：國立科學園區實驗中學C++程式語言自學講義
什麼叫貪婪
貪婪演算法的原文是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個硬幣了!!!
那該怎麼辦，只好試試所有可能的組合
再從裡面找最好的答案了
這個就放在下一章介紹
至於這個單元介紹的所有題目都是可以短視近利貪婪地解決的
能貪婪地解決當然簡單
但能夠分辨出遇到的題目能不能使用貪婪大法
以及該怎麼貪婪
則是這個單元的重頭戲
那麼先來做一道錢幣問題吧
【學生練習題】
其他貪婪題目
【例題】
有一群人要上廁所
輸入總人數，以及每個人所需要的時間
希望讓大家總共的等待時間最小
請安排大家的順序
以及輸出所有人總共等了多久
各位應該都有共識
如果有好幾個人同時想要用廁所
大家會說「用最快的先去」
或是會毛遂自薦「我用很快，先讓我去」
因為如果讓用得久的先去
其他人就必須等他很久
但讓用得快的先去
其他人就只需要等他一下下
因此這題只要讓大家依照時間順序排好
並且對於每個人都去計算「排在他前面的所有人時間總合」
就會是它需要等待的時間
再把所有人的等待時間相加起來就是答案了
【學生練習題】
再看看下一題
【例題】
你有好幾本書
希望把他們釘成一大本
所以你拿到書匠的店去
書匠的規則是一次只能把其中兩本釘在一起
而且收的錢是兩本書頁數的和
(因為如果頁數和愈大，他就必須用愈大的釘子)輸入你的書有幾本
以及每一本書原本有幾頁
請安排最適合的釘書順序
以及輸出最少需要付的錢
因為每次都是拿兩本書給書匠釘成一本
所以可以每次都很短視近利地拿最薄的兩本給他
當他釘完後
把新的書放進原書堆裡
再從裡面抓最薄的兩本出來給他釘
一直到所有書都被釘成同一本為止
例如像這樣
你有四本書
分別是2頁、3頁、4頁、7頁
一開始先拿2頁和3頁的釘起來，花費5元
於是你所有的書變成
5頁、4頁、7頁
這時再拿5和4釘起來，花費9元
變成9頁、7頁
最後再把9和7釘起來，花費16元
總共需要花費5+9+16=30元
30元絕對是最少的花費了
其他釘法一定不可能比30還要低
【學生練習題】
經典問題：最大連續元素和
雖然他被歸類在動態規畫
但我認為他明明就是貪婪演算法…
題目是這樣的
【例題】
老師的心情陰晴不定
有時候會幫你加分
有時候會把你扣分
因此為了避免被扣分
還是請假最好
但你又希望加分的時候可以來上課賺分數而上課的規則是你只能來連續的一段時間
不能中間請假後來又跑來已知老師每一天哪天會加多少分、哪天會扣多少分了
請安排一段時間連續來上課，並且可以得到最多分數
請輸出最多的分數
例如有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的這段和
【學生練習題】
下一章是動態規劃
其中就會介紹到如果不能每次都短視近利
(例如最上面提到的最少硬幣組合)
必須比較所有可能的組合時
該怎麼有效率地解決
上一章：排序
下一章：動態規劃
回目錄：國立科學園區實驗中學C++程式語言自學講義
