# 貪婪演算法 Greedy

----


---

## 上題目 ~
### [悠閒的超商店員](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b034)

在一個國家中，有 9 種面額的硬幣，分別是
1、5、10、50、100、500、1000、5000、10000
請問要湊出 $x$ 元，至少要用幾個硬幣

----

## 隨便想一下

硬幣數要最少，就先選大的吧~

----

啊 過了

----

## 下課

---

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" (不用連續)