---
# System prepended metadata

title: 貪婪演算法(greedy algorithm)

---

# 貪婪演算法(greedy algorithm)
貪婪演算法，又稱貪心演算法

貪婪演算法在每一步決策中選擇當前看似最好的選項，目的在尋找**局部最優解**而非一定為**全局最優解**

給個例子，你有若干個1元、5元、10元硬幣，如果需要湊出16元，最少需要幾個硬幣？

`coins = 0, cnt = 0`
優先選擇最大面額(10元)
`coins = 1, cnt = 10`
10元會超出所求，選擇第二高面額(5元)
`coins = 2, cnt = 15`
最後選擇1元
`coins = 3, cnt = 16`

故答為 `3`

## 例題
:::success
### [ntucpc- [Tutorial] 好吃的蛋糕](https://oj.ntucpc.org/problems/97)
:::
:::spoiler 解題思路
將好吃度排序，並從最大開始加總$K$個，最後輸出
:::
:::spoiler WA
注意數字的大小
:::
:::success
### [ntucpc- [Tutorial] 趕不完的作業](https://oj.ntucpc.org/problems/98)
:::
:::spoiler 解題思路
一樣排序，但要考慮作業的截止時間，並且要在寫完一份作業後改變當前時間
:::
:::warning
### [ntucpc- [Tutorial] 趕不完的作業2](https://oj.ntucpc.org/problems/99)
:::
:::spoiler 解題思路
記得「模擬」寫作業過程經過的時間，並且考慮做一份作業後接下來還可以做哪些
:::
:::warning
### [ntucpc- 1072 . A.誰先晚餐](https://tioj.ck.tp.edu.tw/problems/1072)
:::
:::spoiler 解題思路
每個人吃完一份餐的速度必為$t+C_i+E_i$分鐘，因此邊計算$max$邊模擬做菜過程即可
:::
:::spoiler tips
「多組測試資料」
:::
:::warning
### [ntucpc- 713 . 餐點順序](https://oj.ntucpc.org/problems/713)
:::
:::spoiler 解題思路
實際推演後可以發現到，||先做花費時間少的為局部最優解||
:::
:::info
### <font color = "#9894F9"> 武陵高中114學科能競校內初選- pF Restaurants Around WLSH </font>
(沒有連結只是好看)
此題無judge，公開測資對則正確
###### ~~小小碎碎念：這題會留著是因為我打完這些說明後發現沒有judge，但我打很久所以留下來了~~
:::
#### **Description**：
:::spoiler Description
零換粥是一名五零高中的學生，有一天晚上他留下來和同學吃飯，正當他們踏出校門時，他們遇到了世紀三大謎題之一———「晚餐要吃什麼」。身為五零老屁股，零換粥拿出了珍藏的美食餐廳清單，上面依序寫了他對每間餐廳的喜好度排名。為了不要白跑一趟，他們打算先查好每間餐廳有沒有開，再去喜好度排名最前面（數字最小）的餐廳。已知每間餐廳分別被編號為$1 ∼ N$ ，現在給你這份美食餐廳清單，以及每間餐廳的營業狀況，請你判斷他們應該要去哪間餐廳吃飯。
:::

#### **Input**
:::spoiler Input
輸入的第一行是一個正整數 $N$，代表餐廳的數量。第二行有$N$ 個正整數，其中第 $i$ 個整數 $x_i$ 代表第 $i$ 間餐廳的喜好度排名。第三行有 $N$ 個正整數，皆為 $1$ 或 $0$ ，其中第 $i$ 個整數 $y_i$ 代表第 $i$ 間餐廳的營業狀況（$1$ 代表有營業，$0$ 代表沒有營業）。
* $1 ≤ N ≤ 10^6$
* 對於所有$1 ≤ i ≤ N，1 ≤ x_i ≤ N$ ，保證$x_i$ 互不相同。
* 對於所有$1 ≤ i ≤ N，yi ∈ \{0, 1\}$ ，保證至少有一個$y_i$ 為 $1$。
:::
#### **Output**
:::spoiler Output
輸出一個整數，代表他們最後選擇的餐廳的編號（亦即所有有營業的餐廳中，排名最前面的餐廳的編號）。
:::

#### **Samples**
:::spoiler Samples
| Sample No. | Input                                                                        | Output |
|:---------- |:---------------------------------------------------------------------------- |:------ |
| 1          | 3 <br> 2 3 1 <br> 0 1 0                                                      | 2      |
| 2          | 10 <br> 1 2 3 4 5 6 7 8 9 10 <br> 1 1 1 1 1 1 1 1 1 1                        | 1      |
| 3          | 15 <br>9 15 4 10 13 6 2 12 5 8 7 1 14 3 11 <br>0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 | 15     |
:::
:::danger
### [CSES- Tasks and Deadlines](https://cses.fi/problemset/task/1630/)
:::
#### 題目敘述翻譯
你有 $n$ 個任務要處理，且每個任務都須完成不能不做。
每個任務都有持續時間 $a$ 和截止日期 $d$。
每完成一個任務，會獲得 $(\ d-完成時間f\ )$ 的收益，此數值有可能為負
如果你採取最優行動，你的最大收益總和是多少？
:::spoiler 解題思路
對於局部最優解而言，選擇先做持續時間短的比做截止日期近的較優，類似「誰先晚餐」的解題思路，持續時間會影響到後續的幅度比日期多。

因此此題應先將資料按照持續時間由小排到大，再根據題目做運算

###### ~~注意: 資料範圍~~~~
:::
>[!NOTE]...待新增...
