or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
貪心
Greedy
10/23 preTraining
前言 –- greedy 是甚麼鬼?
核心概念 –- 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 通常分為兩種
對於分步驟類型題目
對於靜態的,排列類型的題目
通常難在"如何想到並證明一個好的偏序關係(排序方式)",找到偏序關係後通常就直接照著此偏序關係排序,然後剩下就好好做完就好,例如例題 NPSC筆電自動機 以及去年 ICPC Taoyuan site pF
如何構造比較方法?
一般而言會從 \(n = 2\) 時開始考慮,當只有 2 個物件時的比較方法,再推廣到多個物件(但須判斷是否符合偏序關係)
也就是去思考每個 case 對於答案的貢獻以及對於前後者的影響,考慮清楚之後 greedy 的式子就會浮現在腦中
經典題目時間
Q1 最大線段互斥集
給定 \(n\) 條線段 (\(l_i\) ∼ \(r_i\)),選出盡量多條線段,其中這些線段不得重疊。
以下有幾種狀況(排序方法)來決定 greedy 選擇線段的順序:
請問哪一個是對呢 :)
實際操作只需要排序後就 greedy 選取即可(若當前線段與已選線段重疊則捨棄,反之則選取)
狀況1的反例
狀況3的反例
至於狀況 4 以及 5 根本就是在唬爛。
Q2 單機排程問題
有 \(n\) 份工作,每份工作有所需時間 \(t_i\) 與期限 \(d_i\),求是否能找到一個工作順序使得可以在期限內完成所有工作。
直觀的想法:
又是哪一個選項呢(歪頭笑
- 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 的證明。首先,先假設有一組是能如期完成所有工作的排序 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\) 個
因此接下來考慮應該
捨棄第 \(i\) 個工作
選擇做第 \(i\) 個工作,並移除前面選的某一項工作
已知為了後面好,在同樣只能完成 \(k\) 個工作的情況下,應該要盡量減少總工作時間,因此移除這 \(k+1\) 個工作中工時最長的工作是最好的選擇(前提是剩餘 \(k\) 個工作皆能完成,但根據我們的假設,這並沒問題)
再來是證明移除這 \(k+1\) 個工作中工時最長的,
剩下 \(k\) 個工作必能準時完成
由於前 \(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,在過程中先選起來當前最佳
之後遇到更好的就反悔選更好的。