Greedy Method

中文譯作「貪心法」，以Incremental Method或Iterative Method來製造答案的方法，大致上分為兩類：

一、填答案（Incremental Method）：
　　從沒有答案開始，逐步填滿答案，
　　每次根據現況算出一部分答案，直到答案都填滿為止。

二、改答案（Iterative Method）：
　　先隨便弄個答案，逐步修飾答案，
　　每次根據現況修飾一部分答案，直到答案夠漂亮為止。

用這般投機取巧的手段，自以為能獲得正確答案，實在是太貪心了，故得名「貪心法」。

Greedy性質

當一個問題真的可以這樣胡搞瞎搞弄出正確答案，就稱這個問題「有Greedy性質」。有Greedy性質的問題，能以Greedy Method求出正確答案。

天底下哪有這麼碰巧的問題？就是有這麼碰巧的問題！想盡辦法利用這種碰巧，把正確答案算出來，這真的是貪心十足了，不愧名為「貪心法」。

用Greedy Method設計演算法時的步驟

1. 觀察問題特徵，擬定一個填答案＼改答案的原則。
2. 隨便挑幾個特例，手算一下。如果答案都對，就採用此原則。
   （也可以嘗試證明此原則必定正確。）
3. 實作程式碼，把答案算出來。

觀察問題所展露的性質，舉幾個單純的例子，然後根據這些例子，猜測一個簡單的計算方法。若這些單純的例子能算出正確答案，就大膽假設複雜的例子可以用一樣的方式，漸進地算出正確答案。

範例：Change-Making Problem（找零錢）

你去商店買東西，你掏出了一張一百元，買了一包23元的零食。櫃員須找零錢給你，但是你希望櫃員找給你的硬幣數目越少越好，如此口袋會輕一點。那麼櫃員會給你幾個硬幣呢？

填答案的原則是：先找給你面額較高的硬幣。

Matroid

要證明一個問題是否有Greedy性質，數學領域已經建立一套稱做「Matroid」的數學模型，可以用於證明，不過有些Greedy性質是無法使用Matroid的。這方面的知識頗為艱深，故此處省略之。

UVa 120 311 410 514 538 668 719 757 10020 10037 10148 10201 10249 10366 10382 10440 10602 10716 10718 10982

UVa 10020 10148

荷蘭國旗問題

http://www.iis.sinica.edu.tw/~scm/ncs/2010/10/dutch-national-flag-problem/

http://www.iis.sinica.edu.tw/~scm/ncs/2010/10/dutch-national-flag-problem-2/

http://www.iis.sinica.edu.tw/~scm/ncs/2010/10/dutch-national-flag-problem-3/

換零錢問題

到商店買東西後，店員要找錢。如何讓找的銅板（暨紙鈔）個數最少？

演算法（Cashier's Algorithm）

這個方法非常直覺，盡量先找面額大的銅板即可。時間複雜度是O(N)，N是銅板種類。

int price[5] = {50, 20, 10, 4, 2}; // 面額由大到小排列 void cashier(int n) // n 是總共要找的錢。 { int c = 0; for (int i=0; i<5; ++i) while (n >= price[i]) { n -= price[i]; // 找了 price[i] 元 c++; } if (n != 0) cout << "找不出來"; else cout << "找了" << c << "個錢幣"; } int price[5] = {50, 20, 10, 4, 2}; void cashier(int n) { int c = 0; for (int i=0; i<5; ++i) { c += n / price[i]; n %= price[i]; } if (n != 0) cout << "找不出來"; else cout << "找了" << c << "個錢幣"; }

UVa 166

適用情況（Pearson's Algorithm）

現實生活中，錢幣面額是經過精心設定的，可以安心使用Cashier's Algorithm。

不幸的消息是，並不是任意一種面額組合，都可以使用Cashier's Algorithm。要使用Cashier's Algorithm，得先經過驗證才行：

一、各種價錢都能找，不會有找不出來的情況。
二、錢幣用量真的是最少的。

時間複雜度是O(N^3)。

【問題描述】
一組錢幣面額 (c1, c2, ..., cn)，幣值大小順序是 c1 < c2 < ... < cn。
找出不適用貪心法的最小價位 M。也就是 1 ~ M-1 用貪心法是對的。
正確湊得 M 的最少錢幣用量為 (b1, b2, ..., bn)，稱呼為正確湊法 b 或者 b(M)。
貪心湊得 M 的最少錢幣用量為 (g1, g2, ..., gn)，稱呼為貪心湊法 g 或者 g(M)。

【性質甲】正確湊法有最佳子結構（包含關係）
若湊法 x 已經是最佳解，
則比 x 小的 y 統統都是最佳解（x >= y，每一個對應項都是大於等於）。
最短路徑截一段還是最短路徑的意思。

【性質乙】貪心湊法是嚴格遞增函數（字典順序關係）
貪心湊法當中，價錢較大的湊法，字典順序會大於價位較小的湊法。
（以高項次代表高位數。）
也就是說 g(X) 函數嚴格遞增，而 b(1 ~ M-1) = g(1 ~ M-1) 也是嚴格遞增。

【性質丙】b(M) 與 g(M) 剛好不相交
b(M) AND g(M) EQUAL (0, 0, 0, ...., 0)
b(M) 和 g(M) 對應的項不會同時有值，因為拿掉這些錢幣，M 就可以更小，矛盾。
這個性質不會用到。

【證明開始】
令 s 是 b(M) 最小的非零項索引值，t 是 b(M) 最大的非零項索引值。
也就是 b(M) = (0, ... , 0, bs, ... , bt, 0, ... , 0)，
bs 與 bt 都大於零，bs 的左邊都是零，bt 的右邊都是零。

【證明步驟一】M 之下限
貪心湊法總是由較大的面額開始湊。
湊 M 出錯的時候，一定是拿了比 ct 更大的面額來湊。
所以 M 至少會有 ct+1 那麼大。M >= ct+1。

【證明步驟二】M 之上限
正確的湊 M 不會用到 ct+1，正確的湊 (M - cs) 當然也不會用到 ct+1。【性質甲】
湊 (M - cs) 時貪心也會對。【M的前提】
貪心湊法總是由較大的面額開始湊。
沒有用到 ct+1，表示 (M - cs) 太小了，所以 (M - cs) < ct+1。
（也可以推得 (M - ct) < ct+1 ，不過他比較寬鬆，用不到。）

【證明步驟三】觀察 (ct+1 - 1) 的湊法。使用夾擠。
M > (ct+1 - 1) >= (M - cs)　【步驟一二】
g(M) > g(ct+1 -1) >= g(M - cs)，如果 g(M) 是對的湊法。【性質乙】
但是事實上 g(M) 是不對的，所以只好改成相似的：
b(M) > g(ct+1 - 1) >= b(M - cs)

【步驟三補充】證明 b(M) > g(ct+1 - 1 - ct) 在第 t 項加一
因為 b(M - ct) = g(M - ct)   >   b(ct+1 - 1 - ct) = g(ct+1 - 1 - ct)
剛好 ct 是最大的非零項，所以會滿足【逆向性質甲】，故在第 t 項加一即得證。
剛好 ct 是最大的非零項，也滿足貪心湊法的規則，
所以 g(ct+1 - 1 - ct) 在第 t 項加一，就正是 g(ct+1 - 1) 了。

【證明步驟四】
b(M) 與 b(M - cs) 幾乎一樣。【性質甲】【M的前提】

        b(M)        = ( ..., 0 , gs    , ... , gt, 0 , ... )
     >  g(ct+1 - 1) = ( ???, ? , gs - 1, ... , gt, 0 , ... )
     >= b(M - cs)   = ( ..., 0 , gs - 1, ... , gt, 0 , ... )

g(ct+1 - 1) 被夾在中間，根據字典順序關係【性質乙】，從第 s 項以上都是確定值。
反過來說，求出 g(ct+1 - 1)，就可以嘗試推理出 b(M) 和 b(M - cs) 的值。

【演算法】
M = +oo
for i = 1 to n
    算 g(ci+1 - 1) = b(ci+1 - 1)。  // 一定是對的湊法。
    for j = 1 to i                  // 窮舉第 s 項的位置。
      算 b(X)，讓 g(ci+1 - 1) 第 j-1 項以下都變成零，讓第 j 項加一，即得。
      算 X。
      算 g(X)。
      if g(X) 與 b(X) 的錢幣用量相同（項次不同沒關係）
          X可以湊出正確值，不是我們要的。不做任何事。
      else
          更新 M，M = min(M, X)。
return M

穩定婚姻問題

一家婚友社將N位男士與N位女士進行媒合，一位男士配一位女士，共要撮合N對婚姻。

每位男士各自擁有一個好感度列表，對N位女性各以1到N的數字進行排名。每位女士各自亦有一個好感度列表，對N位男性各以1到N的數字進行排名。

媒合時必須避免，不是伴侶的某男某女，出現婚外情的傾向：「男對女說：我愛你比愛我妻子還深。同時女對男說：我愛你比愛我丈夫還深。」請找出適合的配對方式。

演算法（Gale-Shapley Algorithm）

這個問題已被證明恰有兩解（或一解，當此兩解相同時），其中一解稱為男士最佳解，另一解則稱為女士最佳解。男士最佳解的演算法如下：

1. N位男士各自向自己最喜愛的女士求婚。
2. N位女士各自從自己的求婚者中，挑最喜愛的那位男士訂婚，但是往後可背約。
   沒有求婚者的女士，就只好等等。
3. 失敗的男士們，只好各自向自己次喜愛的女士求婚。
4. N位女士各自從自己的求婚者中，挑最喜歡的那位男士訂婚，但是往後可背約。
   已訂婚卻有更喜愛的男士求婚的女士，就毀約，改為與此男士訂婚。
　 沒有求婚者的女士，就只好再等等。
5. 重複3. 4.直到形成N對伴侶為止。

男士不斷降格以求，女士不斷水漲船高，最後達成平衡。

女士最佳解的演算法則改為由女士主動求婚即可。

時間複雜度是O(N^2)。

UVa 11119

過橋問題

月黑風高的夜晚，有一座不長不短的獨木橋，只能同時容兩人併行。

此時正好有四個寂寞難耐、悲苦淒涼，事實上是窮極無聊的四個人路經此地。他們手邊僅帶著一支手電筒，想要通過這危險的獨木橋。那橋下可是暗潮洶湧，一失足便成千古恨，奔流到海不復回。

幸好四人閒閒沒事就常走這座橋，對路況簡直熟悉到不行，閉著眼睛走都可以，於是乎四人知道自己過橋分別需時1分鐘、2分鐘、5分鐘、10分鐘。但是不管他們的腳程不可思議的快、莫名其妙的慢，四人都是貪生怕死之徒，手上沒有握著手電筒的話，誰都不敢過橋；四人也都是視財如命之徒，就是誰也不想浪費錢，去附近的便利商店買支手電筒，寧可摔到水裡隨波逐流環遊世界去。

最後他們只好協議說，一次兩人同時持手電筒過橋，再請其中一人送回手電筒，沒事做的人就在橋邊哭爹喊娘等手電筒回來，如此一來四人最終都能夠順利過橋。

兩人同時過橋時必須配合走得慢的人的速度，請問全員過橋最快要多久時間？有一些規矩你是知道的，例如不能把手電筒用丟的丟過河，不能四個人疊羅漢一起過橋，不能把橋拆了做木筏之類的。

演算法

腳程快的人送手電筒回來那是最好的；相對地，腳程慢的人就應該讓他留在彼岸不要回來。不管先走後走，人人都還是要過橋，所以先試試看把腳程最慢的人送到對岸吧！

當人數眾多，至少四人時，令A與B是最快與次快，C與D是次慢與最慢。讓最慢的兩個人過橋主要有兩種方式，第一種是AB去A回、CD去B回，第二種是AD去A回、AC去A回， 至於其它方式所花的時間恰好跟這兩種方式一樣。採用比較快的那一種方式，讓最慢的兩個人過橋之後，問題範疇就縮小了。

時間複雜度是排序腳程快慢以及掃描一次所有數據所需的時間。

// 各個人的腳程由慢到快排序 int a[8] = {1, 2, 5, 10, 15, 16, 30, 31}; void bridge_and_torch() { int n, t = 0; for (n=8-1; n>=3; n-=2) { int t1 = a[0] + a[1]*2 + a[n]; int t2 = a[0]*2 + a[n-1] + a[n]; t += min(t1, t2); } if (n == 2) t += a[0] + a[1] + a[2]; else if (n == 1) t += a[1]; else t += a[0]; cout << "所有人過橋的總時間為" << t; }

UVa 10037

問題

有一位苦命上班族，要馬上處理臨時指派的N份工作。經驗老到的他，馬上就精準的估計出每份工作各要花掉多少時間，可是每份工作都有不同的完工期限，這造成有些工作可能會來不及完成。他做事專心，要求品質，一次只處理一份工作，一份一份接著做；來不及完成的工作，乾脆放棄不做。

請找出一種排程，讓如期完成的工作最多（也就是讓逾期完成的工作最少）。

合理解之相鄰兩兩交換性質

一個合理排程，其中某兩個如期完成的工作A與B，A早做B晚做，B緊接A之後做。如果A的期限較晚，B的期限較早（與A期限相同也無妨），則A與B對調位置之後，仍會是一個合理排程。證明如下：

一、A與B交換，把A與B視作一體，其他工作的起始時間和結束時間皆不受影響。

二、考慮A放到B的位置：A的期限比B還晚，B都能如期完成了，所以A也能如期完成。

三、考慮B放到A的位置：B提早做，更能如期完成。

有了此性質，不管是哪一種合理排程，都可以經過相鄰兩兩交換，形成一個照期限排序的合理排程。也因此，我們可以先將所有工作按照期限排序，然後依此順序加入排程，是有機會求得合理結果的。

註：不相鄰則不可貿然交換。

UVa 10026

演算法（Moore-Hodgson Algorithm）

可以找出其中一種合理排程，而且還是總工時最短的排程。

時間複雜度為O(NlogN)，為一次排序的時間，加上維護Priority Queue的時間。

1. 完工期限由小到大排序。
2. 逐一把工作加入排程。
   每次加入工作後，一旦發現逾期，立即從排程當中抽掉工時最長的工作。
3. 排程當中的工作，做為如期完成的工作。
   中途抽出來的工作，則不做。（或者做為逾期完成的工作，排在所有工作之後。）

在步驟2.當中，
令目前加入排程的工作有N個，目前仍留在排程裡的工作有M個。

排程所記錄的工作，隨時都會是前N個工作的最佳解。也就是說：
α. 前N個工作當中，能如期完成的工作數目，最多就是M。
β. 目前的排程，是前N個工作當中，完成M個工作，總工時最短的排程。
γ. 排程裡的工作們，每一件工作都保持如期完成。

使用數學歸納法證明，只提重點。第N+1個工作加入排程，有兩種情形。

一、沒有發生逾期（即是如期）：

M個工作是總工時最短的，加入一個成為M+1個，依然是總工時最短，αβγ都成立。

二、發生了逾期，立即抽出工時最長的工作：

剛加入工作但還未抽出工作時，此時總工時已經最短了，卻還是逾期，無法增加M，因此α成立。

一加一抽後，仍是M個工作，但是總工時必會盡力下降（可能不變，如果抽出的是第N+1個工作），β成立。

新加入的工作，因為期限排序，其期限更晚，又加上總工時盡力下降，所以新加入的工作能夠如期完成；原來的M-1個工作們，本來就能如期完成，抽出一個工作後，更能如期完成了。因此M個工作都可以如期完成，γ成立。

struct Job {int time, due;} job[10]; priority_queue<int> pq; bool cmp(const Job& j1, const Job& j2) { return j1.due < j2.due; } void Moore_Hodgson() { sort(job, job+10, cmp); int t = 0; for (int i=0; i<10; ++i) { pq.push(job[i].time); t += job[i].time; if (t > job[i].due) t -= pq.top(), pq.pop(); } cout << "如期完成的工作數目，最多為" << pq.size(); cout << "逾期完成的工作數目，至少為" << 10 - pq.size(); } struct Job { int time, due; bool operator<(const Job& j) const { return due < j.due; } } job[10]; int heap[10], size = 0; void Moore_Hodgson() { sort(t, t+10); int t = 0; for (int i=0; i<10; ++i) { heap[size++] = job[i].time; push_heap(heap, heap+size); t += job[i].time; if (t > job[i].due) { t -= heap[0]; pop_heap(heap, heap+size); size--; } } cout << "如期完成的工作數目，最多為" << size; cout << "逾期完成的工作數目，至少為" << 10 - size; }

UVa 10154

問題

兩台機器，N份工作，一台機器一次只能處理一個工作。每份工作必須先經過初號機處理一段時間，再經過貳號機處理一段時間，才算處理完畢。

請找出一種排程，迅速完成所有工作。

演算法（Johnson's Rule）

時間複雜度O(NlogN)，取決於排序的時間。

1. 建立兩個空的List，叫做L1和L2。
2. 從N個工作、2N個工時當中，不斷挑出工時最短的工作。
   如果最短工時是初號機的工時，該工作加到L1後端。
   如果最短工時是貳號機的工時，該工作加到L2前端。
3. L1 L2，即是排程。

1. 建立兩個空的List，叫做L1和L2。
2. 對每一個工作，若初號機工時小於貳號機工時，該工作加到L1，反之則加到L2。
3. L1照初號機工時由小到大排序。
   L2照貳號機工時由大到小排序。
4. L1 L2，即是排程。

【待補證明】

int c1[10]; int c2[10]; bool cmp1(const int& i, const int& j) {return c1[i] < c1[j];} bool cmp2(const int& i, const int& j) {return c2[i] > c2[j];} void Johnson() { vector<int> l1, l2; for (int i=0; i<10; ++i) if (c1[i] < c2[i]) l1.push_back(i); else l2.push_back(i); sort(l1.begin(), l1.end(), cmp1); sort(l2.begin(), l2.end(), cmp2); vector l = l1 + l2; int t1 = 0, t2 = 0; for (int i=0; i<l1.size(); ++i) { t1 += c1[l[i]]; t2 = max(t1, t2) + c2[l[i]]; } cout << "總完成時間為" << t2 << endl; }

UVa 11269 11729