---
tags: FD Training
---

# 貪婪法(Greedy)

---

## 核心概念
- 顧名思義:貪婪
- 題目屬於最佳化問題
- 假設一個問題可以分成很多步驟，那麼每一輪都選擇當前最好的那一個
- 或者如果問題是要排列東西使得最大/小化某個目標函數，那麼可以找到一種比較函數(偏序關係)，用它排序後即為正解
- 可以greedy的題目都相對容易實作，但是要證明greedy是正確的並不容易

----

### 範例 Add All
https://zerojudge.tw/ShowProblem?problemid=b606
從一堆數字中，不斷選出兩個數字相加，成本為其總和，並將相加後的數字丟回數字中，求最後剩下一個數字時的最小成本
解法應該很直觀，就是每輪不斷地從中選出兩個最小的數字相加，直到最後剩下一個數字

----

由於每輪都是選當前最佳選項(讓當次操作成本最低)，而且一直做下去就是最佳解，因此本題為greedy題(是最佳解的證明略過)
這題實作上是用priority_queue，一開始把所有東西丟進去，每次把最小的兩個取出來，相加加進成本並把結果丟回priority_queue，直到只剩一個數字
複雜度$O(n\lg n)$

----

### NPSC筆電自動機

現在有一些題目，已知每題的所需時間，排列出解題順序使得總penalty最小，一個題目的penalty計算方式從一開始到解完該題的時間總和，也就是前面解的題目+當前題目的時間總和
很直觀的作法就是由快而慢寫，也就是直接由小排到大(證明略過)
因此一開始sort完然後好好計算penalty即可

---

## 實作方法

----

### 對於分步驟類型的題目
- 通常分成"靜態"與"動態"兩種，其中靜態指的是每輪操作後，那些東西不會再被修改，而動態則是每輪操作後會有修改，例如Add All
- 對於靜態的題目，通常一開始用指定方法sort完後由前做到後即可
- 對於動態的題目，通常需要用priority_queue，一開始把所有東西丟進去，之後每輪取最佳解出來並做修改(再丟東西進priority_queue之類的)

----

### 對於排列類型的題目
- 通常難在"如何想到並證明一個好的偏序關係(排序方式)"，找到後通常就直接照著此排序方式排序，然後剩下就好好做完就好，例如NPSC筆電自動機

----

### 如何構造比較方法
一般而言會從$n=2$時開始考慮，當只有2個物件時的比較方法，再推廣到多個物件(但須判斷是否符合偏序關係)

----

### 如何證明greedy的正確性
雖然有一些判斷方法，但難以一一細說，因此可能需要多寫題目累積經驗
常見的方法為反證法，假設存在一組最佳解其排列異於你的比較方法，然後證明將其改成照著你的比較方式排列必然不會變差

---

## 經典題目

----

### 最大線段互斥集
給定$n$條線段($l_i\sim r_i$)，選出盡量多條線段，其中這些線段不得重疊。
以下有幾種排序方法來決定greedy選擇線段的順序:
1. $l$由小排到大
2. $r$由小排到大
3. $r-l$(長度)由小排到大

----

實際上只有第2個是好的，因此對所有線段以$r$排序，之後就greedy選取即可(若當前線段與已選線段重疊則捨棄，反之則選取)
以$l$排序的反例:$n=3,1\sim5,2\sim3,4\sim5$
以$len$排序的反例:$n=3,1\sim5,4\sim7,6\sim10$

----

### 單機排程問題
有$n$分工作，每份工作有所需時間$t_i$與期限$d_i$，求是否能找到一個工作順序使得可以在期限內完成所有工作。
直觀的想法:
1. 先做時間短的，也就是排序$t_i$
2. 先做期限近的，也就是排序$d_i$

----

實際上2是好的，1是爛的(反例:$(1,3),(2,2)$)
證明:假設存在一組排列能如期完成所有工作，但其中至少存在一組相鄰項$i,i+1$其前項的期限比較長:$d_i>d_{i+1}$
所有工作如期完成:$s_{0...j}\le d_j,\forall j$
交換第$i$與$i+1$項只會對$d_i,d_{i+1},s_i$造成影響
由於$s'_{0...i+1}=s_{0...i+1}\le d_{i+1}<d_i=d'_{i+1}$因此新的第$i+1$項可以準時完成
由於$s'_{0...i}=s'_{i+1}-t'_{i+1}<s_{i+1}\le d_{i+1}=d'_i$因此新的第$i$項可以準時完成
其餘項$s,d$皆無影響因此皆能準時完成

----

因此得證，若存在排列能如期完成所有工作，但有相鄰項違反$d_i<d_{i+1}$，那麼將兩項交換必然也能如期完成所有工作$\Rightarrow 照著d$由小排到大必然能如期完成所有工作$\Rightarrow$此greedy策略是好的

----

### APCS 物品堆疊
有$n$個物品，每個物品有重量$w_i$和取用次數$f_i$，現在要將物品由上而下排列，取用一項物品的成本為其上方所有物品重量總和，求最低成本為何。
解法:
首先假設物品由上而下依照$i$排列，那麼可以列出成本式子
$\sum\limits_{i=0}^{n-1}f_is_i$其中$s_i=\sum\limits_{j=0}^{i-1}w_j$是物品重量的前綴和

----

考慮只有兩項物品($i,j$)時的排列方法:
$i$在$j$上方的成本為$f_i\cdot 0+f_j\cdot w_i=f_j\cdot w_i$
$j$在$i$上方的成本為$f_j\cdot 0+f_i\cdot w_j=f_i\cdot w_j$
將兩者比大小即可決定誰在上誰在下
接下來考慮將相鄰項交換對其他項成本的影響:
$f_i$必不會改變，上下方的$s_i$也不會改變，因此交換相鄰項只會影響此兩項的成本，其他項皆不受影響
$\Rightarrow$不斷比較相鄰項交換是否會比較好
$\Rightarrow$最終狀態等同是用```f[j]*w[i]<f[i]*w[j]```作為比較方法排序的結果

----

### 單機排程問題-進階
有$n$分工作，每份工作有所需時間$t_i$與期限$d_i$，最多能準時完成多少份工作?(其餘工作可以捨棄不做)
從前面的證明可以得知，假設決定好要選做哪些工作，那麼將$d$由小排到大便能確認是否能全部準時完成
因此一開始就先將所有工作照$d$由小排到大，剩下就只需要考慮要選哪些工作而已

----

假設前$0\sim i-1$項中最多只能準時完成$k$個工作，且其中一組最佳解是做$a_1,a_2,...,a_k$這$k$個工作(此$k$個工作皆能準時完成)，現在考慮第$i$個工作(欲求前$i$項工作最多能準時完成多少個):
若直接將第$i$個工作加進去能準時完成(也就是$\sum\limits_{j=1}^{k}t_{a_j}+t_i\le d_i$)那麼就將它加進去，因此前$i$項工作最多能準時完成$k+1$個
反之代表前$i$項工作最多只能完成$k$個

----

因此接下來考慮應該
1. 捨棄第$i$個工作
2. 選擇做第$i$個工作，並移除前面選的某一項工作

已知為了後面好，在同樣只能完成$k$個工作的情況下，應該要盡量減少總工作時間，因此移除這$k+1$個工作中工時最長的工作是最好的選擇(前提是剩餘$k$個工作皆能完成)

----

再來是證明移除這$k+1$個工作中工時最長的，剩下$k$個工作必能準時完成
1. 如果工時最長的是$i$，很明顯捨棄$i$可以符合條件
2. 反之假設移除了$a_j$這項工作，已知那$k-1$項工作必能準時完成(原本$k$項都能準時完成了，工作減少一定也能準時完成)，因此只須考慮第$i$個工作
$由於前k項皆能準時完成:\sum\limits_{j=1}^{k}t_{a_j}\le d_k且d_k\le d_i$與$t_i\le t_{a_j}$
$\Rightarrow\sum\limits_{j=1}^{k}t_{a_j}-t_{a_j}+t_i\le\sum\limits_{j=1}^{k}t_{a_j}\le d_k\le d_i$

----

得證，移除第$a_j$項工作後，第$i$項工作可以準時完成$\Rightarrow$剩下的$k$個工作皆能準時完成
因此實作上就是用個priority_queue去維護前面已選的工作的工時，依序考慮每一個工作，如果加入該工作可以準時完成則直接加入，反之則加入後並移除其中工時最長的工作，做到最後priority_queue的大小即為所求(此外priority_queue內數字總和是在滿足最大化準時完工數量的條件下，最短的總工時)