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