程序員算法基礎(chǔ)——貪心算法

前言

貪心是人類自帶的能力，貪心算法是在貪心決策上進(jìn)行統(tǒng)籌規(guī)劃的統(tǒng)稱。

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

有n個盒子排成一行，每個盒子上面有一個數(shù)字a[i]，表示最多能向右跳a[i]個盒子；

小明站在左邊第一個盒子，請問能否到達(dá)最右邊的盒子？

比如說：[1, 2, 3, 0, 4] 可以到達(dá)第5個盒子；

[3, 2, 1, 0, 4] 無法到達(dá)第5個盒子；

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

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

正文

貪心算法基礎(chǔ)概念

狹義的貪心算法指的是解最優(yōu)化問題的一種特殊方法，解決過程中總是做出當(dāng)下最好的選擇，因為具有最優(yōu)子結(jié)構(gòu)的特點，局部最優(yōu)解可以得到全局最優(yōu)解；這種貪心算法是動態(tài)規(guī)劃的一種特例。能用貪心解決的問題，也可以用動態(tài)規(guī)劃解決。

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

我們發(fā)現(xiàn)的題目的核心在于向右能到達(dá)的最遠(yuǎn)距離，我們用maxRight來表示；

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

貪心算法的思考過程

貪心的思考過程類似動態(tài)規(guī)劃，依舊是兩步：大事化小，小事化了。

大事化?。?/strong>

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

小事化了：

從小問題找到?jīng)Q策的核心，確定一種得到最優(yōu)解的策略，比如跳一跳中的向右能到達(dá)的最遠(yuǎn)距離；

在證明局部的最優(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ā)，當(dāng)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)；（相當(dāng)于把第5秒到第i秒的時間分配給任務(wù)j）

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

小明在學(xué)校兼職，小明一天兼職的時間有10個小時；

現(xiàn)在有多個兼職崗位，每個崗位有個開始時間和結(jié)束時間，小明同一時間只能做一個兼職；

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

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

為什么？

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

我們天生具備了這種優(yōu)化決策的能力。

3、分糖果問題

n個小朋友玩完游戲后，老師準(zhǔn)備給他們發(fā)糖果；

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

問老師最少準(zhǔn)備多少糖果。

這是一道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)該怎么分配？

答案是：從分?jǐn)?shù)最低的開始。

按照分?jǐn)?shù)排序，從最低開始分，每次判斷是否比左右的分?jǐn)?shù)高。

假設(shè)每個人分c[i]個糖果，那么對于第i個人有c[i]=max(c[i-1],c[c+1])+1;?（c[i]默認(rèn)為0，如果在計算i的時候,c[i-1]為0，表示i-1的分?jǐn)?shù)比i高）

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

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

我們需要對貪心的策略進(jìn)行優(yōu)化：

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

如果只考慮比左邊的人分?jǐn)?shù)高時，容易得到策略：

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

再考慮比右邊的人分?jǐn)?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í)過程，就是對自己的思考進(jìn)行優(yōu)化。

是把握已有信息，進(jìn)行最優(yōu)化決策。

作者：落影l(fā)oyinglin

鏈接：https://www.jianshu.com/p/b613ae9d77ff