# 前言
貪心演算法的意思是挑選目前最好的選擇，換句話說就是有一個固定的規則可以解決問題，因為有時候挑選目前最好的選擇不一定是全局最好的。舉例來說我們有很多工作，每個工作的工作時間不同 (ex:8 點到 9 點，12 點到 16 點) 可是每個工作給我們帶來的效益是相同的，我們要怎麼在有限的時間裡安排工作讓我們可以獲得最大效益，換句話說就是在盡可能安排更多工作，我們該怎麼安排工作呢？在那麼多個工作中該怎麼挑選工作才是最佳解呢？
貪心最讓人卡關的地方，往往不是「怎麼寫」，而是「為什麼這樣貪心是對的」。我原本的講義在這裡大多是「自己嘗試證明看看」，這章補上 2023 CISCON《貪心 Greedy》課程（Koying）裡系統化的證明方法：反證法跟交換論證。
# 貪心是什麼
不斷選擇「目前」最好的選項。這句話聽起來像廢話，但它精確地描述了貪心演算法的行為：每一步只根據當下能看到的資訊做決定，且做了決定就不會反悔。
# 硬幣問題：貪心不一定對
先看一個經典反例，體會貪心為什麼需要證明。
硬幣問題 1：你有無限多個面額為 1, 5, 10, 50 的硬幣，請問要怎麼用最少的硬幣數量湊出 n 元？
相信有買過東西的人應該都知道該怎麼辦，顯然就是先拿面額大的。但，這個策略難道永遠都是正確的嗎？
硬幣問題 2：你有無限多個面額為 1, 5, 11 的硬幣，請問要怎麼用最少的硬幣數量湊出 n 元？
使用剛剛的策略還會正確嗎？假設 n=15，使用剛剛的策略會拿 11+1+1+1+1 （5 枚），但是 5+5+5 才是最少的硬幣數量（3 枚）。代表著這個策略並不是永遠正確的，或許只有在硬幣面額呈倍數時才成立。
這說明了貪心演算法沒有一套萬用的判斷方法，每一題的貪心規則是否正確，都需要個別驗證。那該如何證明呢？以下會介紹一些在離散數學中比較常見的證明方式。
# 貪心法的常見證明方式
# 反證法（Proof by Contradiction）
給出某命題 p 與 p̄（非 p），其滿足排中律（(p ∨ ¬p) 為真，也就是 p 與非 p 至少有一為真）。假設 p̄ 成立，但經過推導後我們發現 p̄ 並不成立，那麼就代表 p 成立。
用一個大家高中都學過的例子來體會這個技巧：證明 √2 為無理數（無法使用兩互質整數 p, q 將其表示為 p/q）。
- 假設 √2 為有理數，那麼根據有理數的性質，
√2 = p/q - 移項之後：
2q^2 = p^2 - 則
2 | p^2，又因此可推導出2 | p，所以我們可以將 p 寫成2k - 再套回去剛剛的式子：
q^2 = 2k^2，因此2 | q - 經過上面的推導，發現 p, q 皆為偶數，但是 p, q 互質，所以 p, q 不能同時為偶數，矛盾
- 因此 √2 為無理數
在貪心法中，反證法的用法是：先假設「貪心解不是最佳解」，然後推導出矛盾（例如發現存在一個比貪心解更好的解，但這個解其實可以被貪心解取代或超越），從而證明貪心解必定是最佳解。
# 回到硬幣問題：什麼時候貪心解是最佳的
有無限多個面額為 c_1, c_2, ..., c_n 的硬幣，請問要怎麼用最少的硬幣數量湊出 x 元？已知 v_1 = 1 ， v_i | v_{i+1} （ v_i 能夠整除 v_{i+1} ）。
- 假設對於某個
c_i的硬幣，我們用了超過c_{i+1}/c_i個，那麼我們就可以將這c_{i+1}/c_i個c_i換成是c_{i+1} - 根據以上所述，每個硬幣的數量都不會超過
c_{i+1}/c_i個，且在最佳解中，若只使用c_1 ~ c_{i-1}的硬幣，所能湊出的最大金額為v_i - 1 - 因此當我們需要求出 x 元，且
c_i ≤ x < c_{i+1}時，必選c_i，得證在面額倍數關係時，貪心解為最佳解
這正好解釋了為什麼「1, 5, 10, 50」用貪心是對的（每個面額都是前一個的倍數），而「1, 5, 11」不是（11 不是 5 的倍數）。
# 數學歸納法（Mathematical Induction）
數學歸納法的步驟還蠻簡單的：
- 證明 n=1 時成立
- 當 n=m 時，證明 n=m+1 時成立
有點類似我推倒第一張骨牌，接下來每一張骨牌都會因前一張骨牌倒下而倒下。
舉平方和公式的證明作為範例，試證明 Σ(i=1 to n) i^2 = n(n+1)(2n+1)/6 ：
- n=1 時，成立（左式 = 1，右式 =
1×2×3/6 = 1） - 當 n=m 時，假設
Σ(i=1 to m) i^2 = m(m+1)(2m+1)/6成立 - 則 n=m+1 時，
Σ(i=1 to m) i^2 + (m+1)^2 = m(m+1)(2m+1)/6 + (m+1)^2 = m(m+1)(2m+1)/6 + 6(m+1)(m+1)/6= (m+1)(m+2)(2m+3)/6，滿足 n=m+1 時的式子- 由數學歸納法得證
數學歸納法也可以用來證明遞迴定義的性質，例如證明費式數列 Σ(i=0 to n) F_i = F_{n+2} - 1 ：
- n=0 時，
F_0 = F_2 - 1，成立 - 假設 n=m 時成立，此時
Σ(i=0 to m) F_i = F_{m+2} - 1 - 在 n=m+1 時，可得
Σ(i=0 to m+1) F_i = F_{m+2} - 1 + F_{m+1} - 可得
Σ(i=0 to m+1) F_i = F_{m+3} - 1 - 由數學歸納法得證
# 構造性證明（Constructive Proof）
利用建立出一種構造方式，證明假設正確。
例如證明質數有無限多個：
- 假設已知質數有 k 個
p_1, p_2, ..., p_k - 那麼我們就可以構造出一個數
x = ∏(1 to k) p_i + 1 - 如果 x 為和數，那麼一定可以找到一個質因數 P 使得
P | x - 但這是不可能的，因為
x ≡ 1 (mod p_i)，所以 x 為質數，得證
構造性證明在貪心法裡常用來直接建構出一個解，並證明這個解等於或優於貪心解，藉此確立貪心解的下界。
# 交換論證（Exchange Argument）：貪心法最常用的證明方式
回頭看我原本講義裡的兩題貪心，其實它們背後的證明方式都是交換論證：假設有一個非貪心的最佳解，證明把它「換成貪心的順序」不會讓答案變差，於是貪心解至少跟最佳解一樣好。
# 例題：CSES Movie Festival
題目來源：CISCON 2023 貪心課程
有 n 場電影，每場電影從 a_i 到 b_i ，請問最多可以看幾場電影？（n ≤ 2×10^5）
觀察題目，發現可能會有兩種方式：依照開頭排序、依照結尾排序。
依開頭排序的情況：很簡單的可以發現，若有一部特別早開始的電影，但是特別晚結束，那麼這部電影的時間就很有可能包含了其他部電影，導致不會是最佳解。
依結尾排序：假設我們目前在 x 之後有空，那麼根據策略，看了一部最早結束的電影 i 之後，變為 b_i 之後有空。對於任意一個解所看的電影 j 看完後有空的時間變為 b_j ， b_i 必定 ≤ b_j 。顯然在剩下的時間內， b_i 之後所能看的電影數量必定 ≥ b_j 之後所能看的電影數量。
得證不存在另一優於貪心解 ⇒ 貪心解為最佳解。
// [來源：本文補充，待替換] | |
sort(movies.begin(), movies.end(), [](auto& x, auto& y){ | |
return x.second < y.second; // 依照結尾（b）排序 | |
}); | |
int count = 0; | |
long long lastEnd = LLONG_MIN; | |
for (auto& [a, b] : movies){ | |
if (a >= lastEnd){ | |
count++; | |
lastEnd = b; | |
} | |
} |
這個證明的結構完全就是交換論證：任意一個候選解，都可以被「換成貪心的選擇」而不變差。這比我原本講義裡「機器出租」那題的直覺解釋更嚴謹 —— 它明確指出了為什麼「選最早結束的工作」永遠不會比其他選擇差。
# 判斷該用哪種排序：一個實用的觀察角度
上面這個例子點出一個很實用的判斷方式：碰到區間排程類的貪心題，通常會猶豫「要依開頭排序還是依結尾排序」。判斷的關鍵在於：貪心規則挑出來的選項，是不是保證不會排擠掉其他選項的空間。依結尾排序、選最早結束的，可以保證留給後面的空間最大；依開頭排序則沒有這個保證，因為開頭早不代表結尾也早。
# 貪心經典題
# 最大子陣列和：也可以用貪心
給一個整數陣列 A [0:n-1]，請計算 A 的連續子陣列的最大可能總和，空陣列的和以 0 計算。
還記得區間和怎麼算嗎？ Σ(i=l to r) a_i = psum_r - psum_{l-1} 。對於 r 為結尾的最大子陣列和，顯然就是一個最小的 psum_i 滿足 i < r 。那麼對於整個陣列的最大子陣列和，答案就是 max(r=1 to n) (psum_r - min(i=1 to r-1) psum_i) 。
這其實跟貪心的精神一致：掃過陣列時，隨時記錄「目前看過的最小前綴和」，用當前前綴和減掉它就是以當前位置結尾的最大子陣列和，全程只需要 O(n) ，且每一步都在做「目前最好的選擇」（選最小的前綴和當基準點）。這題也是分治法的經典題，會在 1-7 分治演算法 用不同的角度再解一次。
# 機器出租（APCS）
有 N 個活動，舉辦每個活動都要租借一台機器，若要舉辦第 N 個活動，就需要在時間段 [L,R] 租借用一台機器的。已知 N 個活動的需要使用的時間段，並且有 K 台機器可以開放租借，且一台機器同時間只能借給一個活動，請問最多可以成功舉辦多少場活動？
輸入說明：第一行有兩個正整數 N 和 K。第二行有 N 個正整數，第 i 個正整數是活動 i 的開始時間 L。第三行有 N 個正整數，第 i 個正整數是活動 i 的結束時間 R。
| 範例輸入 #1 | 範例輸出 #1 |
|---|---|
| 5 1 0 2 1 3 4 2 3 5 4 6 |
2 |
| 範例輸入 #2 | 範例輸出 #2 |
| 8 2 3 1 4 3 7 2 2 5 5 3 7 4 8 7 4 6 |
5 |
這一題一開始看可能會覺得有點難，我們有時候遇到比較難的題目可以先把題目拆解成比較簡單的版本然後一步一步去思考，像是這題可以先假設 K=1，這樣整個題目就變成只有單一機器要如何去安排工作的問題，該如何安排呢？這是一個貪心法則很經典的問題，就是挑選最早結束的工作，一直不斷地挑選最早結束的工作 —— 這正是上面「CSES Movie Festival」的交換論證能直接套用的地方。
我們已經知道 K=1 的情況下要挑選最早結束的工作那如果 k>1 該怎麼辦，那就每台機器都挑選最早結束的工作，可是這樣做其實還有一個小問題就是每個的工作時間起始點都不一樣，要怎樣才能讓機器選擇時間能更有彈性呢？我們已經知道挑選最早結束的工作，再來要挑選要讓哪個機器來做這個工作，挑選那個機器工作完離現在這個工作的開始時間最接近的，這樣就整理玩了。
// [自己的解法] | |
#include<bits/stdc++.h> | |
using namespace std; | |
#define N 100005 | |
bool cmp(pair<int,int> a,pair<int,int> b){ | |
return a.second<b.second; | |
} | |
int n,k,ans; | |
multiset<int> ms; | |
pair<int,int> pii[N]; | |
int main(){ | |
ios::sync_with_stdio(0); | |
cin.tie(0); | |
cin>>n>>k; | |
for(int i=0;i<n;i++) | |
cin>>pii[i].first; | |
for(int i=0;i<n;i++) | |
cin>>pii[i].second; | |
sort(pii,pii+n,cmp); | |
for(int i=0;i<k;i++) ms.insert(-1); | |
for(int i=0;i<n;i++){ | |
auto it=ms.lower_bound(pii[i].first); | |
if(it==ms.begin()) continue; | |
it--;// 第一個小於現在工作開始的時間 | |
ans++; | |
ms.erase(it); | |
ms.insert(pii[i].second); | |
} | |
cout<<ans; | |
} |
# 物品堆疊（APCS）
將 N 個物品堆在一個垂直的貨架上，每個物品各佔一層。系統運作的方式如下：每次只會取用一個物品，取用時必須先將在其上方的物品貨架升高，取用後必須將該物品放回，然後將剛才升起的貨架降回原始位置，之後才會進行下一個物品的取用。每一次升高貨架所需要消耗的能量是以這些物品的總重來計算。
現在有 N 個物品，第 i 個物品的重量是 w (i) 而需要取用的次數為 f (i)，我們需要決定如何擺放這些物品的順序來讓消耗的能量越小越好。
| 範例輸入 #1 | 範例輸出 #1 |
|---|---|
| 2 20 10 1 1 |
10 |
| 範例輸入 #2 | 範例輸出 #2 |
| 3 3 4 5 1 2 3 |
19 |
解釋一下範例輸入 #2：最佳解由上到下依序是 (3,2,1)，所以最上面的重量 5 要取用三次就不需要移除箱子，再來往下的箱子要移動兩次上面箱子的重量是 5 所以乘 2，再來最下面的箱子要移動一次所以需要移開上面的兩個箱子，所以是 (4+5)*1 再加上之前箱子消耗的能量 9+10 所以答案是 19。
首先不要把題目想的太難，思考貪心法則的目的是尋求當前的最佳解，所以你可以把相鄰的兩個箱子調換看看，看調換後有沒有比較好，拿上面得範例輸入 #2 的例子，假設預設是 (1,2,3)，我們先來判斷後面的 2 跟 3 要不要調換，要怎麼判斷呢？根據題目就是自己的頻率去乘上對方的重量，按照這樣排序從小排到大。
這其實就是交換論證的實作版本：任取相鄰兩個物品 i、j，比較「i 在上、j 在下」跟「j 在上、i 在下」哪種花費比較少，可以推出最佳排序滿足 w_i × f_j < w_j × f_i （也就是按 w × f 由小到大排）。這個「比較相鄰兩者交換前後的差異」正是交換論證的標準操作程序，之後遇到類似的排序類貪心題都可以照這個方法推導。
// [自己的解法] | |
#include<bits/stdc++.h> | |
using namespace std; | |
#define N 100005 | |
struct item{ | |
int w,f; | |
}; | |
bool cmp(item p,item q){ | |
return p.w*q.f < q.w*p.f; | |
} | |
int main(){ | |
item ite[N]; | |
int n; | |
cin>>n; | |
for(int i=0;i<n;i++) | |
cin>>ite[i].w; | |
for(int i=0;i<n;i++) | |
cin>>ite[i].f; | |
sort(ite,ite+n,cmp);// 按照上述的解釋排序 | |
long long all=0,buffer=ite[0].w;// 記得用 long long | |
for(int i=1;i<n;i++){ | |
all+=buffer*ite[i].f; | |
buffer+=ite[i].w;// 重量是累加的 | |
} | |
cout<<all; | |
return 0; | |
} |
# 先到先服務（AP325）
有 n 個客人要分配到 m 個櫃台來服務，客人依編號順序到達，第 i 個客人需要 t (i) 的時間來完成 (無論分配到哪一個櫃台)，而且每個客人的需求必須在同一個櫃台完成。因為公平的因素，先到客人不可以比晚到客人更晚開始服務。現在希望安排每個客人的服務櫃檯，以便可以在最短的時間內完成所有客人的需求。
輸入說明：輸入兩行，第一行是正整數 n 與 m，第二行是 n 個正整數 t (1),t (2),…,t (n)，同行數字間以空白隔格。n 與 m 不超過 2×10^5，t (i) 不超過 1×10^4。
輸出說明：最早可能服務完所有客人的時間。
| 範例輸入 #1 | 範例輸出 #1 |
|---|---|
| 3 2 3 1 5 |
6 |
下面程式的利用了加上負號的技巧來讓優先佇列由小到大來方便解題。
// [自己的解法] | |
#include<bits/stdc++.h> | |
using namespace std; | |
int main(){ | |
int n,m,mx=0; | |
priority_queue<int> pq; | |
cin>>n>>m; | |
for(int i=0,buffer;i<n;i++){ | |
cin>>buffer; | |
if((int)pq.size()<m) | |
pq.push(-buffer);// 遵守先到先服務 | |
else{ | |
buffer+=-(pq.top()); | |
pq.pop(); | |
pq.push(-buffer); | |
} | |
mx=max(mx,buffer); | |
} | |
cout<<mx; | |
} |
用 priority_queue<int> 存負值，取出來的 top() 就是「所有櫃台中，目前累積工時最小的那一個」（因為負值最大等於原值最小）。每來一位客人，就分配給目前最早有空的櫃台，這正是貪心的直接應用 —— 永遠把新工作分給目前負擔最輕的資源。
# 小結
貪心演算法的思路很直覺（挑眼前最好的），但 **「直覺」不等於「正確」**，硬幣問題就是最好的反例。這章的重點是給出幾套系統化的驗證方法：
| 證明方式 | 核心手法 | 適合的貪心類型 |
|---|---|---|
| 反證法 | 假設貪心解不是最佳解，推出矛盾 | 需要說明「最佳解一定包含貪心的選擇」 |
| 數學歸納法 | 證明小規模成立，再證明從 m 到 m+1 也成立 | 遞迴定義或可以逐步累加的性質 |
| 構造性證明 | 直接構造一個達到或優於目標的解 | 需要確立下界或存在性 |
| 交換論證 | 任取一個解，證明「換成貪心的選擇」不會變差 | 排序類、區間排程類貪心（最常見） |
實務上寫貪心題最常用的是交換論證：先猜一個排序規則，再拿相鄰兩個元素做交換，比較交換前後哪個比較好，往往就能推出正確的排序條件。這比空想或死背規則可靠得多。
下一章要講掃描線演算法，它常常是貪心思路的延伸 —— 排序之後，由一個方向掃到另一個方向，一路上維護當前需要的資訊。
# 練習題
（之後補上）
