前言

貪心是人類自帶的能力，貪心算法是在貪心決策上進行統籌規劃的統稱。

[[231562]]

比如一道常見的算法筆試題----跳一跳：

• 有n個盒子排成一行，每個盒子上面有一個數字a[i]，表示最多能向右跳a[i]個盒子;
• 小明站在左邊第一個盒子，請問能否到達最右邊的盒子?
• 比如說：[1, 2, 3, 0, 4] 可以到達第5個盒子;
• [3, 2, 1, 0, 4] 無法到達第5個盒子;

我們自然而然能產生一種解法：盡可能的往右跳，看最后是否能到達。

本文即是對這種貪心決策的介紹。

正文

貪心算法基礎概念

狹義的貪心算法指的是解最優化問題的一種特殊方法，解決過程中總是做出當下最好的選擇，因為具有最優子結構的特點，局部最優解可以得到全局最優解;這種貪心算法是動態規劃的一種特例。能用貪心解決的問題，也可以用動態規劃解決。

而廣義的貪心指的是一種通用的貪心策略，基于當前局面而進行貪心決策。以跳一跳的題目為例：

• 我們發現的題目的核心在于向右能到達的最遠距離，我們用maxRight來表示;

此時有一種貪心的策略：從第1個盒子開始向右遍歷，對于每個經過的盒子，不斷更新maxRight的值。

貪心算法的思考過程

貪心的思考過程類似動態規劃，依舊是兩步：大事化小，小事化了。

大事化小：

一個較大的問題，通過找到與子問題的重疊，把復雜的問題劃分為多個小問題;

小事化了：

從小問題找到決策的核心，確定一種得到最優解的策略，比如跳一跳中的向右能到達的最遠距離;

在證明局部的最優解是否可以推出全局最優解的時候，常會用到數學的證明方式。

貪心算法的具體應用

1、紙幣找零問題

有1元、2元、5元、10元的紙幣分別有a[1], a[2], a[3], a[4]張，要用這些紙幣湊出m元，至少要用多少張紙幣?

如果是動態規劃：

• 要湊出m元，必須先湊出m-1、m-2、m-5、m-10元，我們用dp[i]表示湊出i元的最少紙幣數;
• 有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1;
• 容易知道dp[1]=dp[2]=dp[5]=dp[10]=1;

根據以上遞推方程和初始化信息，可以容易推出dp[1~m]的所有值。

似乎有些不對?平時我們找零錢有這么復雜嗎?

從貪心算法角度出發，當m>10且我們有10元紙幣，我們優先使用10元紙幣，然后再是5元、2元、1元紙幣。

• 從日常生活的經驗知道，這么做是正確的，但是為什么?
• 假如我們把題目變成這樣，原來的策略還能生效嗎?
• 有1元、5元、7元的紙幣分別有a[1], a[2], a[3]張，要用這些紙幣湊出m元，至少要用多少張紙幣?

接下來我們來分析這種策略：

• 已知對于m元紙幣，1，2，5元紙幣使用了a，b，c張，我們有a+2b+5c=m;

假設存在一種情況，1、2、5元紙幣使用數是x，y，z張，使用了更少的5元紙幣(z

我們令k=5*(c-z)，k元紙幣需要floor(k/2)張2元紙幣，k%2張1元紙幣;(因為如果有2張1元紙幣，可以使用1張2元紙幣來替代，故而1元紙幣只能是0張或者1張)

容易知道，減少(c-z)張5元紙幣，需要增加floor(5*(c-z)/2)張2元紙幣和(5*(c-z))%2張紙幣，而這使得x+y+z必然大于a+b+c。

由此我們知道不可能存在使用更少5元紙幣的更優解。

所以優先使用大額紙幣是一種正確的貪心選擇。

對于1、5、7元紙幣，比如說要湊出10元，如果優先使用7元紙幣，則張數是4;(1+1+1+7)

但如果只使用5元紙幣，則張數是2;(5+5)

在這種情況下，優先使用大額紙幣是不正確的貪心選擇。(但用動態規劃仍能得到最優解)

2、服務器任務安排問題

服務器有n個任務要執行，每個任務有開始時間Si秒和結束時間Ti秒，同一時間只能執行一個任務。

問如何安排任務，使得在時間m內盡可能多的完成任務。

如果是動態規劃：

前i秒的完成的任務數，可以由前面1~i-1秒的任務完成數推過來。

• 我們用dp[i]表示前i秒能完成的任務數;

在計算前i秒能完成的任務數時，對于第j個任務，我們有兩種決策：

1. 不執行這個任務，那么dp[i]沒有變化;
2. 執行這個任務，那么必須騰出來(Sj, Tj)這段時間，那么dp[i] = max(dp[i], dp[ S[j] ] ) + 1;

比如說對于任務j如果是第5秒開始第10秒結束，如果i>=10，那么有dp[i]=max(dp[i], dp[5] + 1);(相當于把第5秒到第i秒的時間分配給任務j)

再考慮貪心的策略，現實生活中人們是如何安排這種多任務的事情?我換一種描述方式：

• 小明在學校兼職，小明一天兼職的時間有10個小時;
• 現在有多個兼職崗位，每個崗位有個開始時間和結束時間，小明同一時間只能做一個兼職;

問小明每天最多能做幾份兼職?

我們自然而然會想到一個策略：先把結束時間早的兼職給做了!

為什么?

因為先做完這個結束時間早的，能留出更多的時間做其他兼職。

我們天生具備了這種優化決策的能力。

3、分糖果問題

n個小朋友玩完游戲后，老師準備給他們發糖果;

每個人有一個分數a[i]，如果比左右的人分數高，那么糖果也要比左右的多，并且每個小朋友至少有一顆。

問老師最少準備多少糖果。

這是一道LeetCode題目。

這個題目不能直接用動態規劃去解，比如用dp[i]表示前i個人需要的最少糖果數。

因為(前i個人的最少糖果數)這種狀態表示會收到第i+1個人的影響，如果a[i]>a[i+1]，那么第i個人應該比第i+1個人多。

即是這種狀態表示不具備無后效性。

如果是我們分配糖果，我們應該怎么分配?

答案是：從分數最低的開始。

按照分數排序，從最低開始分，每次判斷是否比左右的分數高。

假設每個人分c[i]個糖果，那么對于第i個人有c[i]=max(c[i-1],c[c+1])+1; (c[i]默認為0，如果在計算i的時候,c[i-1]為0，表示i-1的分數比i高)

但是，這樣解決的時間復雜度為O(NLogN)，主要瓶頸是在排序。

如果提交，會得到Time Limit Exceeded的提示。

我們需要對貪心的策略進行優化：

• 我們把左右兩種情況分開看。

如果只考慮比左邊的人分數高時，容易得到策略：

• 從左到右遍歷，如果a[i]>a[i-1]，則有c[i]=c[i-1]+1;否則c[i]=1。

再考慮比右邊的人分數高時，此時我們要從數組的最右邊，向左開始遍歷：

• 如果a[i]>a[i+1], 則有c[i]=c[i+1]+1;否則c[i]不變;

這樣講過兩次遍歷，我們可以得到一個分配方案，并且時間復雜度是O(N)。

4、小船過河問題

n個人要過河，但是只有一艘船;船每次只能做兩個人，每個人有一個單獨坐船的過河時間a[i]，如果兩個人(x和y)一起坐船，那過河時間為a[x]和a[y]的較大值。

問最短需要多少時間，才能把所有人送過河。

題目給出關鍵信息：1、兩個人過河，耗時為較長的時間;

還有隱藏的信息：2、兩個人過河后，需要有一個人把船開回去;

要保證總時間盡可能小，這里有兩個關鍵原則：應該使得兩個人時間差盡可能小(減少浪費)，同時船回去的時間也盡可能小(減少等待)。

先不考慮空船回來的情況，如果有無限多的船，那么應該怎么分配?

答案：每次從剩下的人選擇耗時最長的人，再選擇與他耗時最接近的人。

再考慮只有一條船的情況，假設有A/B/C三個人，并且耗時A

那么最快的方案是：A+B去, A回;A+C去;總耗時是A+B+C。(因為A是最快的，讓其他人來回時間只會更長，減少等待的原則)

如果有A/B/C/D四個人，且耗時A

• 最快的來回送人方式，A+B去;A回;A+C去，A回;A+D去; 總耗時是B+C+D+2A (減少等待原則)
• 最快和次快一起送人方式，A+B先去，A回;C+D去，B回;A+B去;總耗時是 3B+D+A (減少浪費原則)

對比方案1、2的選擇，我們發現差別僅在A+C和2B;

為何方案1、2差別里沒有D?

因為D最終一定要過河，且耗時一定為D。

如果有A/B/C/D/E 5個人，且耗時A

仍是從最慢的E看。(參考我們無限多船的情況)

• 方案1，減少等待;先送E過去，然后接著考慮四個人的情況;
• 方案2，減少浪費;先送E/D過去，然后接著考慮A/B/C三個人的情況;(4人的時候的方案2)

到5個人的時候，我們已經明顯發了一個特點：問題是重復，且可以由子問題去解決。

根據5個人的情況，我們可以推出狀態轉移方程dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);

再根據我們考慮的1、2、3、4個人的情況，我們分別可以算出dp[i]的初始化值：

dp[1] = a[1];  
dp[2] = a[2];  
dp[3] = a[2]+a[1]+a[3];  
dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2]); 

由上述的狀態轉移方程和初始化值，我們可以推出dp[n]的值。

這是一道貪心和動態規劃的結合題目，動態規劃的決策過程中用到了貪心的策略。

總結

貪心的學習過程，就是對自己的思考進行優化。

是把握已有信息，進行最優化決策。

這里還有一些收集的貪心練習題，可以實踐練習。