貪心

Greedy

10/23 preTraining

• 核心概念及前言
• 經典例題
• 實作方法及想法
• 經典例題

前言 –- greedy 是甚麼鬼?

• 像 DP(動態規劃) 或 DC(分治) 一樣都是用小問題歸納大問題
• 可以 greedy 的題目都相對容易實作，但是要證明 greedy 是正確的並不容易，所以課程內容大部份為數學證明
• 在賽中容易想到一種 greedy 解，但很容易是假解，所以要考慮它的正確性。
• 能 greedy 的題目大部分都可以 DP 解，但還是要考慮時間、空間複雜度，以及實作難度

核心概念 –- greedy 的必知知識

• 題目屬於最佳化問題，也就是你使用某一種策略，總是可以獲得最好的結果
• 假設一個問題可以分成很多步驟，那麼每一輪(次)都選擇當前最好的那一個
• 通常會是問題若要排列東西使得最大/小化某個目標函數，那麼可以找到一種比較函數(偏序關係)，用它排序後即為正解

簡單範例題 Add All

題意 : 給整數 \(n\) 代表 \(n\) 個數字，從 \(n\) 個數字中，不斷選出兩個數字相加，並將數字和加到cost 裡，並將相加後的數字丟回數字堆中，求最後剩下一個數字時的最小 cost

解法 : 解法應該很直觀，就是每輪不斷地從中選出兩個最小的數字相加，直到最後剩下一個數字

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

簡單範例題 NPSC筆電自動機

題意 : 現在有一些題目，已知每題的所需時間，排列出解題順序使得總penalty最小，一個題目的 penalty 計算方式從一開始到解完該題的時間總和，也就是前面解的題目 + 當前題目的時間總和(時間是一直在走的)

解法 : 很直觀的作法就是由快而慢寫，也就是直接由小排到大(證明可以自己想想看，也是使用反證法)
因此一開始 sort 完然後好好計算 penalty 即可

由於 penalty 的算法就是很直接地加上去，因此先解決最快可解決的題目會讓後面的題目更快被解決使得 penalty 最小，而一直選擇最小數字就是最佳解，因此此題為 greedy 題，證明與上一題 add all 類似。

實作方法

Greedy 通常分為兩種

• 步驟類型(動態、靜態)
• 排序類型

對於分步驟類型題目

• 通常分成"靜態"與"動態"兩種，是對於原本的資料是否有修改。
• 其中靜態指的是每輪操作後，原資料不會再被修改，所以可以直接排序一次過後做到底。而動態則是每輪操作後會有修改，例如例題 Add All
• 對於靜態的題目，通常一開始用指定方法sort完後由前做到後即可
• 對於動態的題目，通常需要用 priority_queue，一開始把所有東西丟進去，之後每輪取最佳解出來並做修改(再丟東西進 priority_queue 之類的)

對於靜態的，排列類型的題目

通常難在"如何想到並證明一個好的偏序關係(排序方式)"，找到偏序關係後通常就直接照著此偏序關係排序，然後剩下就好好做完就好，例如例題 NPSC筆電自動機 以及去年 ICPC Taoyuan site pF

如何構造比較方法?

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

也就是去思考每個 case 對於答案的貢獻以及對於前後者的影響，考慮清楚之後 greedy 的式子就會浮現在腦中

經典題目時間

• 最大線段互斥集
• 單機排程問題
• APCS 物品堆疊
• 單機排程問題 plus

Q1 最大線段互斥集

給定 \(n\) 條線段 (\(l_i\) ∼ \(r_i\))，選出盡量多條線段，其中這些線段不得重疊。
以下有幾種狀況(排序方法)來決定 greedy 選擇線段的順序:

1. l 由小排到大
2. r 由小排到大
3. r - l (長度) 由小排到大
4. l + r (index) 從小排到大
5. r - l (長度) 從大排到小

請問哪一個是對呢 :)

實際操作只需要排序後就 greedy 選取即可(若當前線段與已選線段重疊則捨棄，反之則選取)
狀況1的反例

3
1 5
2 3
4 5

狀況3的反例

3
1 5
4 7
6 10

至於狀況 4 以及 5 根本就是在唬爛。

Q2 單機排程問題

有 \(n\) 份工作，每份工作有所需時間 \(t_i\) 與期限 \(d_i\)，求是否能找到一個工作順序使得可以在期限內完成所有工作。

直觀的想法:

1. 先做時間短的，也就是排序 \(t_i\)
2. 先做期限近的，也就是排序 \(d_i\).
3. 根據他們的最晚開始時間排序，也就是排序 \(d_i - t_i\)
4. 感覺不是 greedy 很像 DP
   又是哪一個選項呢(歪頭笑
   Image Not Showing Possible Reasons

   • The image file may be corrupted
   • The server hosting the image is unavailable
   • The image path is incorrect
   • The image format is not supported

   Learn More →

這邊給出 1 和 3 的反例 :

2 2
1 3

並且提供 2 的證明。首先，先假設有一組是能如期完成所有工作的排序 arr ，並對所有 arr 有一 \(i\) ( \(1\) \(\le\) \(i\) \(<\) \(n\) ) ，且\(d_i\) \(>\) \(d_{i+1}\).
對於一個能如期完成所有工作的arr，會有\(s_{1...j}\) (\(\sum_{i=1}^{j}\limits {t_i}\)) \(\le\) \(d_j\) , \(∀\)\(j\)

交換第 \(i\) 與 \(i+1\) 項只會對 \(d_i\) , \(d_{i+1}\) , \(s_i\) 造成影響由於 \(s^′_{0...i+1}\) = \(s_{0...i+1}\) \(\leq\) \(d_{i+1}\) \(<\) \(d_i\) = \(d^′_{i+1}\)
因此新的第 \(i+1\) 項是可以準時完成，且整體更優於原方案的偏序.
其餘項 \(s\),\(d\) 皆無影響因此皆能準時完成

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

Q3 APCS 物品堆疊

有 \(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\) \(\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\) 也不會改變，因此交換相鄰項只會影響此兩項的成本，其他項皆不受影響

\(\to\) 不斷比較相鄰項交換是否會比較好
\(\to\) 最終狀態等同是用 \(f[j]\cdot w[i]<f[i]\cdot w[j]\) 作為比較方法(排序的偏序關係)

Q4 單機排程問題 進階版

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

假設前 \(0\sim i−1\) 項中最多只能準時完成 \(k\) 個工作，且其中一組最佳解是做
\(a_1\) , \(a_2\),…,\(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_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 內數字總和是在滿足最大化準時完工數量的條件下，最短的總工時)

這種類型的的題目也叫做反悔 greedy，在過程中先選起來當前最佳
之後遇到更好的就反悔選更好的。