<style> .reveal .slides { text-align: left; font-size:30px; } </style> # Greedy Method ## 貪心法 10/20 preTrain ---- ### Table of Contents - 核心概念及前言 - 經典例題 - 實作方法及想法 - 經典例題 --- ## 前言 --- greedy 是什麼鬼? - Greedy 是一種策略，一種設計演算法的方法 - 當問題分很多步驟時，每個步驟都挑選「當前最佳」的解 ---- ## 常遇到的 greedy 都是些什麼? - 可以 greedy 的題目都相對容易實作 - 但是要證明 greedy 是正確的並不容易，所以必修課程內容大部份為數學證明 (用歸納法) - 在賽中容易想到一種 greedy 解 - 但很容易是假解，所以要考慮它的正確性 (舉反例) - 能 greedy 的題目大部分都可以 DP 解 - 但還是要考慮時間、空間複雜度，以及實作難度 ---- Greedy 跟 DP(動態規劃)、DC(分治) 一樣都是用小問題歸納大問題  ---- ## 核心概念 --- greedy 的必知知識 - 題目屬於最佳化問題 : 使用某一種策略，總是可以獲得最好的結果 - 假設一個問題可以分成很多步驟，那麼每一輪(次)都選擇當前最好的那一個 - 通常會是問題若要排列東西使得最大/小化某個目標函數，那麼可以找到一種比較函數 (偏序關係)，用它排序後即為正解 --- ### 簡單範例題 [Add All](https://zerojudge.tw/ShowProblem?problemid=b606) 題意 : 給整數 $n$ 代表 $n$ 個數字，從 $n$ 個數字中，不斷選出兩個數字相加，並將數字和加到 cost 裡，並將相加後的數字丟回數字堆中，求最後剩下一個數字時的最小 cost 解法 : 解法應該很直觀，就是每輪不斷地從中選出兩個**最小**的數字相加，直到最後剩下一個數字 ---- 由於每輪都是選當前最佳選項(讓當次操作成本最低)，而且一直做下去就是最佳解，因此本題為 greedy 題，證明則是可以思考一下他的加法總和，只需要把所有東西都列出來即可 (用歸納法證明每次都是最大) 這題實作上是用 priority_queue，一開始把所有東西丟進去，每次把最小的兩個取出來，相加加進成本並把結果丟回 priority_queue，直到只剩一個數字 複雜度 $O(n \log n)$ (priority_queue) ---- ### 簡單範例題 [NPSC筆電自動機](http://203.64.191.163/ShowProblem?problemid=a071) 題意 : 現在有一些題目，已知每題的所需時間，排列出解題順序使得總penalty最小，一個題目的 penalty 計算方式從一開始到解完該題的時間總和，也就是前面解的題目 + 當前題目的時間總和 (時間是一直在走的) 解法 : 很直觀的作法就是由快而慢寫，也就是直接由小排到大 (證明可以自己想想看，也是使用反證法) 因此一開始 sort 完然後好好計算 penalty 即可 ---- 由於 penalty 的算法就是很直接地加上去，因此先解決最快可解決的題目會讓後面的題目更快被解決使得 penalty 最小，而一直選擇最小數字就是最佳解，因此此題為 greedy 題，證明與上一題 add all 類似。 --- ## 實作方法 Greedy 通常分為兩種 - 步驟類型(動態、靜態) - 排序類型 ---- ## 對於分步驟類型題目 * 通常分成"**靜態**"與"**動態**"兩種，是對於原本的資料是否有修改。 * 其中靜態指的是每輪操作後，原資料不會再被修改，所以可以直接排序一次過後做到底。而動態則是每輪操作後會有修改，例如例題 Add All * 對於靜態的題目，通常一開始用指定方法sort完後由前做到後即可 * 對於動態的題目，通常需要用 priority_queue，一開始把所有東西丟進去，之後每輪取最佳解出來並做修改(再丟東西進 priority_queue 之類的) ---- ## 對於靜態的，排列類型的題目 通常難在"如何想到並證明一個好的偏序關係(排序方式)"，找到偏序關係後通常就直接照著此偏序關係排序，然後剩下就好好做完就好，例如例題 [NPSC筆電自動機](http://203.64.191.163/ShowProblem?problemid=a071) 以及古代的 [ICPC Taoyuan site pF](https://icpc2023.ntub.edu.tw/wp-content/uploads/2023/10/ICPC2023-ProblemSet-Hint.pdf) ---- ## 如何構造比較方法? 一般而言會從 $n = 2$ 時開始考慮，當只有 2 個物件時的比較方法，再推廣到多個物件(但須判斷是否符合偏序關係) 也就是去思考每個 case 對於答案的貢獻以及對於前後者的影響，考慮清楚之後 greedy 的式子就會浮現在腦中 --- ## 經典題目時間 - 最大線段互斥集 - 單機排程問題 * APCS 物品堆疊 * 單機排程問題 plus ---- ## Q1 [最大線段互斥集](http://203.64.191.163/ShowProblem?problemid=a076) 給定 $n$ 條線段 ($l_i$ ∼ $r_i$)，選出盡量多條線段，其中這些線段不得重疊。 以下有幾種狀況(排序方法)來決定 greedy 選擇線段的順序: 1. l 由小排到大 2. r 由小排到大 3. r - l (長度) 由小排到大 4. l + r (index) 從小排到大 5. r - l (長度) 從大排到小 請問哪一個是對呢 :) ---- 實際操作只需要排序後就 greedy 選取即可(若當前線段與已選線段重疊則捨棄，反之則選取) 狀況1的反例 ```cpp 3 1 5 2 3 4 5 ``` 狀況3的反例 ```cpp 3 1 5 4 7 6 10 ``` 至於狀況 4 以及 5 根本就是在唬爛。 ---- ## Q2 [單機排程問題](http://203.64.191.163/ShowProblem?problemid=a078) 有 $n$ 份工作，每份工作有所需時間 $t_i$ 與期限 $d_i$，求是否能找到一個工作順序使得可以在期限內完成所有工作。 直觀的想法: 1. 先做時間短的，也就是排序 $t_i$ 2. 先做期限近的，也就是排序 $d_i$. 3. 根據他們的最晚開始時間排序，也就是排序 $d_i - t_i$ 4. 感覺不是 greedy 很像 DP 又是哪一個選項呢(歪頭笑 :face_with_hand_over_mouth: ---- 4 是在唬爛 這邊給出 1 和 3 的反例 : ```CPP 2 2 1 3 ``` ---- 以下提供 2 的證明。首先，先把演算法寫出來 : 1. 照期限 $d$ 由小到大排序 2. 設排序結果為 $\pi = \langle\pi_1,\pi_2,\dots,\pi_n\rangle$ 3. 計算 $C_k= \sum_{j=1}^{k}\limits t_{\pi_j} \quad (k=1,\dots,n)$ 對所有 $k$ 都有 $C_k \le d_{\pi_k}$，答案為 **可行**；否則 **不可行** ---- Claim : 存在一個可行順序 **若且唯若** 演算法跑出的序列 $\pi$ 滿足 : $$ \sum_{j=1}^{k} t_{\pi_j} \le d_{\pi_k},\quad \forall k $$ ---- $\Rightarrow$ : 設 $\sigma$ 為任一**可行**順序，存在兩個相鄰工作 $J_a, J_b\in \sigma$ 使 $d_a>d_b$ 把「$J_a, J_b$ 前的累積時間」設為 $T$ - 原順序 : $J_a$ 完工於 $T+t_a$，$J_b$ 完工於 $T+t_a+t_b$ - 交換後 : $J_b$ 完工於 $T+t_b$，$J_a$ 完工於 $T+t_b+t_a$ 因為原序列可行，所以 - $T+t_b\le T+t_a+t_b\le d_b\Rightarrow$ 交換後 $J_b$ 準時 - 因 $d_b<d_a\Rightarrow T+t_a+t_b\le d_b < d_a\Rightarrow$ 交換後 $J_a$ 準時 交換不破壞可行性，最終得到的序列且仍保持可行 (若 $d_a<d_b$ 則演算法跑出的順序不影響) ---- $\Leftarrow$ : - 將工作依期限升序標成第一小期限、第二小期限、$\cdots$、第 $k$ 小期限 對任一順序，考慮**這 $k$ 個最早期限的工作**在該順序中各自的完工時間，取其中的最大值 $M_k$ - 由上節交換論證可知 : 若我們反覆將相鄰的「期限逆序對」交換成對 $d$ 遞增排序，這些工作對的完工時間不會增加 - 因此演算法會使得 $\langle M_1,M_2,\dots\rangle$ 每一項下不大於任何其他順序 - 反證 : 若演算法的序列在第 $k$ 位違反了條件，即 $C_k = \sum_{j=1}^{k}\limits t_{\pi_j} > d_{\pi_k}$ - 則對任何順序，其對應的 $M_k \ge C_k > d_{\pi_k}$，表示在這 $k$ 件最早期限的工作中，**至少有一件**完工晚於它的期限 - 故不存在任一可行順序 證畢。 ---- 因此得證，若存在排列能如期完成所有工作 但有相鄰項違反 $d_i$ $<$ $d_{i+1}$，那麼將兩項交換必然也能如期完成所有工作 $\Rightarrow$ 照著 $d$ 由小排到大必然能如期完成所有工作 $\Rightarrow$ 此 greedy 策略是好的 ---- 嗯對 greedy 真的很難證，~~好證的方法一般人會看不懂~~ 實際上舉反例會比較快 ---- ## Q3 [APCS 物品堆疊](https://zerojudge.tw/ShowProblem?problemid=c471) 有 $n$ 個物品，每個物品有重量 $w_i$ 和取用次數 $f_i$ ，現在要將物品由上而下排列，取用一項物品的成本為其上方所有物品重量總和，求最低成本為何。 解法: 假設物品由上而下依照 $i$ 排列，可以列出成本式子 $\sum_{i=0}^{n-1}\limits f_is_i$ 其中 $s_i=\sum_{j=0}^{i-1}\limits w_j$ 是物品重量的前綴和 ---- 考慮只有兩項物品 $(i, j)$ 時的排列方法: $i$ 在 $j$ 上方的成本為 : $f_i\cdot0 + f_j\cdot w_i = f_j\cdot w_i$ $j$ 在 $i$ 上方的成本為 : $f_j\cdot0 + f_i\cdot w_j = f_i\cdot w_j$ 將兩者比大小即可決定誰在上誰在下 ---- 接下來考慮將相鄰項交換對其他項成本的影響: $f_i$ 必不會改變，上下方的 $s_i$ 也不會改變，因此交換相鄰項只會影響此兩項的成本，其他項皆不受影響 $\Rightarrow$ 不斷比較相鄰項交換是否會比較好 $\Rightarrow$ 最終狀態等同是用 $f_j\cdot w_i<f_i\cdot w_j$ 作為比較方法 (排序的偏序關係) ---- ## Q4 [單機排程問題 進階版](http://203.64.191.163/ShowProblem?problemid=a081) 有 $n$ 份工作，每份工作有所需時間 $t_i$ 與期限 $d_i$，最多能準時完成多少份工作? (其餘工作可以捨棄不做) 從 Q2 的證明可以得知，假設決定好要選做哪些工作，那麼將 $d$ 由小排到大就能確認是否能全部準時完成 因此一開始就先將所有工作按照 $d$ 由小排到大，剩下就只需要考慮要選哪些工作而已 ---- 假設前 $0\sim i−1$ 項中最多只能準時完成 $k$ 個工作，且其中一組最佳解是做 $a_1,a_2,\cdots,a_k$ 這 $k$ 個工作(此 $k$ 個工作皆能準時完成)，現在考慮第 $i$ 個工作 (欲求前 $i$ 項工作最多能準時完成多少個): 若直接將第 $i$ 個工作加進去能準時完成 (也就是 $\sum_{j=1}^{k}\limits 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_m$ 這項工作，已知那 $k-1$ 項工作必能準時完成(原本$k$項都能準時完成了，工作減少一定也能準時完成)，因此只須考慮第 $i$ 個工作 由於前 $k$ 項皆能準時完成: $\sum\limits_{j=1}^{k}t_{a_j}\le d_k$ 且 $d_k\le d_i \text{ and } t_i\le t_{a_m}$ $\Rightarrow\sum\limits_{j=1}^{k}t_{a_j}-t_{a_m}+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 內數字總和是在滿足最大化準時完工數量的條件下，最短的總工時) 這種類型的的題目也叫做反悔 greedy，在過程中先選起來當前最佳 之後遇到更好的就反悔選更好的。 --- ## 作業 & 練習時間 https://vjudge.net/contest/758772 ---- Any questions?