程序員算法基礎(chǔ)——貪心算法
前言
貪心是人類自帶的能力，貪心算法是在貪心決策上進行統(tǒng)籌規(guī)劃的統(tǒng)稱。
比如一道常見的算法筆試題----跳一跳：
有n個盒子排成一行，每個盒子上面有一個數(shù)字a[i]，表示最多能向右跳a[i]個盒子；
小明站在左邊第一個盒子，請問能否到達最右邊的盒子？
比如說：[1, 2, 3, 0, 4] 可以到達第5個盒子；
[3, 2, 1, 0, 4] 無法到達第5個盒子；
我們自然而然能產(chǎn)生一種解法：盡可能的往右跳，看最后是否能到達。
本文即是對這種貪心決策的介紹。
正文
貪心算法基礎(chǔ)概念
狹義的貪心算法指的是解最優(yōu)化問題的一種特殊方法，解決過程中總是做出當下最好的選擇，因為具有最優(yōu)子結(jié)構(gòu)的特點，局部最優(yōu)解可以得到全局最優(yōu)解；這種貪心算法是動態(tài)規(guī)劃的一種特例。能用貪心解決的問題，也可以用動態(tài)規(guī)劃解決。
而廣義的貪心指的是一種通用的貪心策略，基于當前局面而進行貪心決策。以跳一跳的題目為例：
我們發(fā)現(xiàn)的題目的核心在于向右能到達的最遠距離，我們用maxRight來表示；
此時有一種貪心的策略：從第1個盒子開始向右遍歷，對于每個經(jīng)過的盒子，不斷更新maxRight的值。
貪心算法的思考過程
貪心的思考過程類似動態(tài)規(guī)劃，依舊是兩步：大事化小，小事化了。
大事化小：
一個較大的問題，通過找到與子問題的重疊，把復(fù)雜的問題劃分為多個小問題；
小事化了：
從小問題找到?jīng)Q策的核心，確定一種得到最優(yōu)解的策略，比如跳一跳中的向右能到達的最遠距離；
在證明局部的最優(yōu)解是否可以推出全局最優(yōu)解的時候，常會用到數(shù)學(xué)的證明方式。
貪心算法的具體應(yīng)用
1、紙幣找零問題
有1元、2元、5元、10元的紙幣分別有a[1], a[2], a[3], a[4]張，要用這些紙幣湊出m元，至少要用多少張紙幣？
如果是動態(tài)規(guī)劃：
要湊出m元，必須先湊出m-1、m-2、m-5、m-10元，我們用dp[i]表示湊出i元的最少紙幣數(shù)；
有?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；
根據(jù)以上遞推方程和初始化信息，可以容易推出dp[1~m]的所有值。
似乎有些不對？平時我們找零錢有這么復(fù)雜嗎？
從貪心算法角度出發(fā)，當m>10且我們有10元紙幣，我們優(yōu)先使用10元紙幣，然后再是5元、2元、1元紙幣。
從日常生活的經(jīng)驗知道，這么做是正確的，但是為什么？
假如我們把題目變成這樣，原來的策略還能生效嗎？
有1元、5元、7元的紙幣分別有a[1], a[2], a[3]張，要用這些紙幣湊出m元，至少要用多少張紙幣？
接下來我們來分析這種策略：
已知對于m元紙幣，1，2，5元紙幣使用了a，b，c張，我們有a+2b+5c=m；
假設(shè)存在一種情況，1、2、5元紙幣使用數(shù)是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元紙幣的更優(yōu)解。
所以優(yōu)先使用大額紙幣是一種正確的貪心選擇。
對于1、5、7元紙幣，比如說要湊出10元，如果優(yōu)先使用7元紙幣，則張數(shù)是4；（1+1+1+7）
但如果只使用5元紙幣，則張數(shù)是2；（5+5）
在這種情況下，優(yōu)先使用大額紙幣是不正確的貪心選擇。（但用動態(tài)規(guī)劃仍能得到最優(yōu)解）
2、服務(wù)器任務(wù)安排問題
服務(wù)器有n個任務(wù)要執(zhí)行，每個任務(wù)有開始時間Si秒和結(jié)束時間Ti秒，同一時間只能執(zhí)行一個任務(wù)。
問如何安排任務(wù)，使得在時間m內(nèi)盡可能多的完成任務(wù)。
如果是動態(tài)規(guī)劃：
前i秒的完成的任務(wù)數(shù)，可以由前面1~i-1秒的任務(wù)完成數(shù)推過來。
我們用dp[i]表示前i秒能完成的任務(wù)數(shù)；
在計算前i秒能完成的任務(wù)數(shù)時，對于第j個任務(wù)，我們有兩種決策：
1、不執(zhí)行這個任務(wù)，那么dp[i]沒有變化；
2、執(zhí)行這個任務(wù)，那么必須騰出來(Sj, Tj)這段時間，那么dp[i] = max(dp[i], dp[ S[j] ] ) + 1；
比如說對于任務(wù)j如果是第5秒開始第10秒結(jié)束，如果i>=10，那么有dp[i]=max(dp[i], dp[5] + 1)；（相當于把第5秒到第i秒的時間分配給任務(wù)j）
再考慮貪心的策略，現(xiàn)實生活中人們是如何安排這種多任務(wù)的事情？我換一種描述方式：
小明在學(xué)校兼職，小明一天兼職的時間有10個小時；
現(xiàn)在有多個兼職崗位，每個崗位有個開始時間和結(jié)束時間，小明同一時間只能做一個兼職；
問小明每天最多能做幾份兼職？
我們自然而然會想到一個策略：先把結(jié)束時間早的兼職給做了！
為什么？
因為先做完這個結(jié)束時間早的，能留出更多的時間做其他兼職。
我們天生具備了這種優(yōu)化決策的能力。
3、分糖果問題
n個小朋友玩完游戲后，老師準備給他們發(fā)糖果；
每個人有一個分數(shù)a[i]，如果比左右的人分數(shù)高，那么糖果也要比左右的多，并且每個小朋友至少有一顆。
問老師最少準備多少糖果。
這是一道LeetCode題目。
這個題目不能直接用動態(tài)規(guī)劃去解，比如用dp[i]表示前i個人需要的最少糖果數(shù)。
因為（前i個人的最少糖果數(shù)）這種狀態(tài)表示會收到第i+1個人的影響，如果a[i]>a[i+1]，那么第i個人應(yīng)該比第i+1個人多。
即是這種狀態(tài)表示不具備無后效性。
如果是我們分配糖果，我們應(yīng)該怎么分配？
答案是：從分數(shù)最低的開始。
按照分數(shù)排序，從最低開始分，每次判斷是否比左右的分數(shù)高。
假設(shè)每個人分c[i]個糖果，那么對于第i個人有c[i]=max(c[i-1],c[c+1])+1;?（c[i]默認為0，如果在計算i的時候,c[i-1]為0，表示i-1的分數(shù)比i高）
但是，這樣解決的時間復(fù)雜度為O(NLogN)，主要瓶頸是在排序。
如果提交，會得到Time Limit Exceeded的提示。
我們需要對貪心的策略進行優(yōu)化：
我們把左右兩種情況分開看。
如果只考慮比左邊的人分數(shù)高時，容易得到策略：
從左到右遍歷，如果a[i]>a[i-1]，則有c[i]=c[i-1]+1；否則c[i]=1。
再考慮比右邊的人分數(shù)高時，此時我們要從數(shù)組的最右邊，向左開始遍歷：
如果a[i]>a[i+1], 則有c[i]=c[i+1]+1；否則c[i]不變；
這樣講過兩次遍歷，我們可以得到一個分配方案，并且時間復(fù)雜度是O(N)。
4、小船過河問題
n個人要過河，但是只有一艘船；船每次只能做兩個人，每個人有一個單獨坐船的過河時間a[i]，如果兩個人(x和y)一起坐船，那過河時間為a[x]和a[y]的較大值。
問最短需要多少時間，才能把所有人送過河。
題目給出關(guān)鍵信息：1、兩個人過河，耗時為較長的時間；
還有隱藏的信息：2、兩個人過河后，需要有一個人把船開回去；
要保證總時間盡可能小，這里有兩個關(guān)鍵原則：應(yīng)該使得兩個人時間差盡可能小（減少浪費），同時船回去的時間也盡可能小（減少等待）。
先不考慮空船回來的情況，如果有無限多的船，那么應(yīng)該怎么分配？
答案：每次從剩下的人選擇耗時最長的人，再選擇與他耗時最接近的人。
再考慮只有一條船的情況，假設(shè)有A/B/C三個人，并且耗時A
那么最快的方案是：A+B去, A回；A+C去；總耗時是A+B+C。（因為A是最快的，讓其他人來回時間只會更長，減少等待的原則）
如果有A/B/C/D四個人，且耗時A
1、最快的來回送人方式，A+B去；A回；A+C去，A回；A+D去；總耗時是B+C+D+2A （減少等待原則）
2、最快和次快一起送人方式，A+B先去，A回；C+D去，B回；A+B去；總耗時是 3B+D+A （減少浪費原則）
對比方案1、2的選擇，我們發(fā)現(xiàn)差別僅在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個人的時候，我們已經(jīng)明顯發(fā)了一個特點：問題是重復(fù)，且可以由子問題去解決。
根據(jù)5個人的情況，我們可以推出狀態(tài)轉(zhuǎn)移方程dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);
再根據(jù)我們考慮的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]);
由上述的狀態(tài)轉(zhuǎn)移方程和初始化值，我們可以推出dp[n]的值。
這是一道貪心和動態(tài)規(guī)劃的結(jié)合題目，動態(tài)規(guī)劃的決策過程中用到了貪心的策略。
總結(jié)
貪心的學(xué)習(xí)過程，就是對自己的思考進行優(yōu)化。
是把握已有信息，進行最優(yōu)化決策。
作者：落影l(fā)oyinglin
鏈接：https://www.jianshu.com/p/b613ae9d77ff