# 貪婪演算法 Greedy ---- ![](https://i.imgur.com/cvslXVD.png) --- ## 上題目 ~ ### [悠閒的超商店員](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b034) 在一個國家中，有 9 種面額的硬幣，分別是 1、5、10、50、100、500、1000、5000、10000 請問要湊出 $x$ 元，至少要用幾個硬幣 ---- ## 隨便想一下 硬幣數要最少，就先選大的吧~ ---- 啊 過了 ![](https://i.imgur.com/4od3Vzq.png) ---- ## 下課 --- Greedy演算法的核心就是 ### 貪！ ---- 在當前的情況中作出一個最佳的選擇 並且這個選擇可以帶來最佳的答案 ---- ### 生活中的貪心 1. 爸媽買了布丁，偷偷吃掉老哥的 2. 國中生追女生，一個不夠追兩個 3. 期末公佈成績，A不夠還要A+ 4. 打CF，破台不夠還要破台rk1 > 以上言論出自資訊之芽講義 ---- ### 什麼時候可以貪 ? ---- ### PixelCat : 只要能證明就可以 ---- 以上面那題來說 1、5、10、50、100、500、1000、5000、10000 任何幣值較大的元素，皆為所有較小的元素的倍數 e.g. $1000=500\times2 =100\times10=50\times20$... 因此可得知，目前可選的最大元素，即是最優解 （否則要用更多的硬幣來湊出這個值） ---- ### 微證明 設當前情況總需的金額為 $P$ 所需最少硬幣數為 $f(P)$ 1. 選擇當前可選最大元素 $m$ ， 所需最少硬幣數為 $f(P-m)+1$ 2. 不選擇最大元素 ，且所選最大元素為 $n$ ( $n<m$ 且 $n$ 為 $m$ 的因數 ) 所需最少硬幣數為 $f(P-n)+1$ 3. 設 $m=n\times k$ , ( $k>1$ ) ---- 4. $(P-n)-(P-m)=n\times (k-1)$ 5. 若 $f(P-n)<f(P-m)$ 對於 $f(P-n)$ 比 $f(P-m)$ 多湊的 $n\times (k-1)$ 元 由於 $n$ 為所選最大元素， 因此湊出 $n\times(k-1)$ 元 的硬幣數會 $>=(k-1)$ 因此 $f(P-m)<=f(P-n)+(k-1)$ 又 $k>1$ 故 $f(P-n)<f(P-m)$ 矛盾 ---- ### 什麼時候不能貪 #### [忙碌的超商店員](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b028) 在一個國家中，有 6 種面額的硬幣，分別是 1、5、10、12、16、20 請問要湊出 $x$ 元，至少要用幾個硬幣 ---- ### 土法煉鋼 try try 看 假設 $x=15$ | Greedy | | 正解 | | ----------------- | --- | ------- | | 12 -> 1 -> 1 -> 1 | | 10 -> 5 | | Ans = 4 | | Ans = 2 | 看來是行不通 ### 點此前往 -> [動態規劃](https://hackmd.io/@Paul-Liao/Skp1FHr6O#/) --- ## 再來幾題 ---- ### [CSES Apartments](https://cses.fi/problemset/task/1084/) 有 $n$ 位客人 $m$ 間房間 第 $i$ 位客人願意住進大小為 $s$ 的房間 $A_i-k <=s<=A_i+k$ （ $k$ 是題目給的常數 ） 求最多能有幾位客人入住房間 ---- ### [TIOJ 1072 誰先晚餐](https://tioj.ck.tp.edu.tw/problems/1072) 有 $n$ 個人要吃晚餐 第 $i$ 個人的餐點要煮 $C_i$ 分鐘、要吃 $T_i$ 分鐘 求所有人都吃完最少要花幾分鐘 ---- ### [Codeforces 1509B TMT Document](https://codeforces.com/problemset/problem/1509/B) 給一個由 T 跟 M 組成的字串 $s$ 求是否可以將字串切割成數個 "TMT" (不用連續)