貪心算法大概是算法世界里最容易被低估的一個(gè)。很多人覺得它不過就是“每一步都選最好的”而已聽起來簡單得像是常識(shí)但真正到了面試、競賽或者工程優(yōu)化場景里能不能一眼判斷“這題能不能用貪心”能不能給出讓人信服的正確性證明就完全是另一回事了。我見過不少同學(xué)動(dòng)態(tài)規(guī)劃推得很溜卻在貪心選擇這一步反復(fù)栽跟頭——不是策略選錯(cuò)就是壓根沒意識(shí)到這里藏著一個(gè)需要嚴(yán)格論證的坎。這篇內(nèi)容我就想從基礎(chǔ)出發(fā)把貪心算法的本質(zhì)、適用條件、經(jīng)典場景和證明思路串一遍特別把“背包問題里貪心為什么有時(shí)靈有時(shí)不靈”這件事講透希望能幫正在學(xué)算法的朋友少走一些彎路。1. 貪心算法的直覺局部最優(yōu)如何一步步逼近全局最優(yōu)貪心算法的核心思想用一句大白話說就是每一步都做出當(dāng)前狀態(tài)下看起來最優(yōu)的選擇并且絕不回頭。它不像動(dòng)態(tài)規(guī)劃那樣需要記錄一堆子問題的狀態(tài)并做比較也不像回溯搜索那樣走不通就退回來重試它是一條道走到黑的策略——認(rèn)定一個(gè)規(guī)則每次按這個(gè)規(guī)則挑一個(gè)“局部最優(yōu)解”一路挑到最后把得到的解當(dāng)作全局問題的答案。這種直覺從生活里就能找到大量影子。比如你手里有一堆面額不等的紙幣要給顧客湊出一筆錢你會(huì)本能地先拿最大面額去湊不夠再拿次大的——這就是貪心。再比如趕時(shí)間做項(xiàng)目手頭有好幾個(gè)任務(wù)每個(gè)任務(wù)有截止時(shí)間和收益你通常會(huì)優(yōu)先做收益最高或者最緊急的那個(gè)——這也是貪心。這些直覺之所以普遍是因?yàn)槿祟愒诖蠖鄶?shù)日常決策中天然傾向于“拿當(dāng)下最有利的選項(xiàng)”懶得去窮舉所有未來的可能性。但作為算法設(shè)計(jì)者你必須清醒地認(rèn)識(shí)到一個(gè)事實(shí)貪心策略的“短視”既是它的優(yōu)點(diǎn)也是它的死穴。優(yōu)點(diǎn)在于效率奇高——不需要枚舉不需要回溯通常一次遍歷或一次排序就能出結(jié)果時(shí)間復(fù)雜度往往能做到O(n log n)甚至O(n)死穴在于它壓根不考慮“這一步選下去之后后續(xù)的路會(huì)不會(huì)被堵死”所以一旦一個(gè)問題的全局最優(yōu)解沒辦法由一系列局部最優(yōu)選擇拼出來貪心就會(huì)給出錯(cuò)誤答案。舉個(gè)最直觀的反例。假設(shè)你要找零錢硬幣面額是1元、5元和11元要湊出15元。如果按“先用最大面額”的貪心策略你第一次選11元剩4元只能拿四個(gè)1元總共用了5枚硬幣。但實(shí)際最優(yōu)解是三個(gè)5元只需要3枚。在這個(gè)問題里局部最優(yōu)每次都拿最大面額并沒有導(dǎo)向全局最優(yōu)因?yàn)槟?1元這一“最優(yōu)步”把后面組合出更優(yōu)解的可能性堵死了。這個(gè)例子極其經(jīng)典也極其重要——它提醒我們貪心不是“憑感覺選個(gè)規(guī)則就行”你必須先確認(rèn)這種短視行為在這個(gè)特定問題里不會(huì)造成損失。那什么樣的局部最優(yōu)策略才算安全呢計(jì)算機(jī)科學(xué)家?guī)臀覀兛偨Y(jié)出了兩個(gè)關(guān)鍵性質(zhì)下一個(gè)部分詳細(xì)拆解。2. 貪心策略成立的兩塊基石貪心選擇性質(zhì)與最優(yōu)子結(jié)構(gòu)2.1 貪心選擇性質(zhì)局部最優(yōu)確實(shí)通向全局最優(yōu)貪心選擇性質(zhì)的嚴(yán)格定義是一個(gè)問題如果可以通過一系列局部最優(yōu)的貪心選擇得到全局最優(yōu)解那這個(gè)問題就具備貪心選擇性質(zhì)。換句話說你不需要考慮子問題的全局解是什么只需要在每一步按既定規(guī)則選一個(gè)眼前最優(yōu)的剩下的交給遞歸或迭代去處理最終結(jié)果依然是最優(yōu)的。這個(gè)性質(zhì)的驗(yàn)證通常不是靠肉眼觀察而是需要數(shù)學(xué)證明。常見的證明思路有兩種。第一種叫“交換論證法”先假設(shè)某個(gè)全局最優(yōu)解存在再說明貪心策略的第一步選擇即那個(gè)局部最優(yōu)項(xiàng)一定可以出現(xiàn)在某個(gè)全局最優(yōu)解里——如果當(dāng)前最優(yōu)解里的第一個(gè)元素不是貪心選的元素就把它和貪心元素交換證明交換后的解不會(huì)變差。這樣就能證明“這一步貪心選擇不會(huì)排除最優(yōu)解”然后不斷對(duì)剩余子問題重復(fù)同樣的論證最終數(shù)學(xué)歸納法收尾整個(gè)貪心策略就被證明了。第二種叫“反證法”假設(shè)貪心得到的解不是全局最優(yōu)那一定存在某個(gè)比貪心解更優(yōu)的解然后順著貪心決策的邏輯推導(dǎo)出一個(gè)與數(shù)據(jù)結(jié)構(gòu)或前提條件矛盾的結(jié)論。相比較換論證法反證法的路徑更依賴具體問題但思路是類似的——你要證明“不這么做不會(huì)更好”。2.2 最優(yōu)子結(jié)構(gòu)子問題的最優(yōu)解能拼出原問題的最優(yōu)解貪心算法成立的第二個(gè)前提是問題具備最優(yōu)子結(jié)構(gòu)。這個(gè)概念在動(dòng)態(tài)規(guī)劃里也出現(xiàn)過——一個(gè)大規(guī)模問題的最優(yōu)解可以由其子問題的最優(yōu)解組合而成。貪心和動(dòng)態(tài)規(guī)劃都需要這個(gè)性質(zhì)區(qū)別在于動(dòng)態(tài)規(guī)劃要窮舉所有子問題然后比較取最優(yōu)貪心則只根據(jù)當(dāng)前選擇規(guī)則鎖定一個(gè)子問題直接往里遞歸省掉了全部比較開銷。那要怎么判斷一個(gè)問題有沒有最優(yōu)子結(jié)構(gòu)呢最實(shí)用的方法是嘗試把問題“切一刀”假設(shè)你已經(jīng)做出了某一步選擇把剩下的輸入看作一個(gè)規(guī)模更小的獨(dú)立子問題然后問自己——如果這個(gè)子問題不是最優(yōu)解整個(gè)問題的解還能是最優(yōu)的嗎如果答案是否定的說明這個(gè)分法滿足最優(yōu)子結(jié)構(gòu)如果答案是“子問題用次優(yōu)解也能拼出全局最優(yōu)”那最優(yōu)子結(jié)構(gòu)就不成立貪心和動(dòng)態(tài)規(guī)劃都用不了。有意思的是在我接觸過的實(shí)際問題中“最優(yōu)子結(jié)構(gòu)成立但貪心選擇性質(zhì)不成立”的情況非常常見剛才說的15元找零問題就是典型你無論如何劃分子問題剩下的子問題依然存在最優(yōu)解比如拿完11元后湊4元的最優(yōu)解確實(shí)存在但貪心的第一步選擇本身就不該做。反過來倒很少見到“貪心選擇性質(zhì)成立但最優(yōu)子結(jié)構(gòu)不成立”的情形——如果一個(gè)問題的局部最優(yōu)決策能安全地導(dǎo)向全局最優(yōu)那它背后往往天然具備遞歸分解的結(jié)構(gòu)。這個(gè)觀察幫我在實(shí)戰(zhàn)中快速過濾問題先問最優(yōu)子結(jié)構(gòu)再問貪心選擇性質(zhì)能省下大量試錯(cuò)時(shí)間。3. 分?jǐn)?shù)背包問題為什么這里是貪心算法的完美秀場提到貪心算法背包問題是繞不開的經(jīng)典場景而“分?jǐn)?shù)背包”又是背包家族里最適合用貪心解決的那個(gè)。所謂分?jǐn)?shù)背包指的是一個(gè)背包容量有限你面對(duì)一堆物品每件物品有重量和價(jià)值但物品可以被切割——你可以裝下一個(gè)物品的一部分獲得該部分對(duì)應(yīng)的那部分價(jià)值。這個(gè)設(shè)定看起來有點(diǎn)不現(xiàn)實(shí)但它廣泛抽象了食材配比、任務(wù)切分、資源分配等真實(shí)場景也是理解“單位價(jià)值”這個(gè)貪心指標(biāo)的絕佳入口。3.1 分?jǐn)?shù)背包的貪心策略按單位價(jià)值排序裝填分?jǐn)?shù)背包問題的貪心策略非常直覺化永遠(yuǎn)優(yōu)先裝“單位重量價(jià)值最高”的物品。算法流程可以這樣描述把每件物品按價(jià)值/重量即單位價(jià)值從高到低排序。從高到低依次裝入背包。如果當(dāng)前物品可以完整裝入就全部裝入更新剩余容量如果當(dāng)前物品不能完整裝入就裝入它的一部分把剩余容量用完算法結(jié)束。這個(gè)策略之所以正確可以找一個(gè)很生活化的類比你有個(gè)零食袋只能裝500克東西面前有不同價(jià)位的零食擺在貨架上你當(dāng)然會(huì)優(yōu)先把“每克最貴”的零食裝進(jìn)來裝不下整包時(shí)就買散稱的把袋子裝滿為止。這個(gè)決策鏈里每一步都在把剩余容量花在“單價(jià)最高的東西”上沒有任何理由先裝便宜的再裝貴的——因?yàn)槟且馕吨阍谕热萘肯履玫搅烁俚目們r(jià)值。來看一個(gè)具體算例。假設(shè)背包容量為50有三件物品物品A重量10價(jià)值60單位價(jià)值6物品B重量20價(jià)值100單位價(jià)值5物品C重量30價(jià)值120單位價(jià)值4按單位價(jià)值排序是A B C。貪心過程是先裝A剩余容量40再裝B剩余容量20最后裝C的20/30即2/3個(gè)C得到價(jià)值 (60 100 80 240)。我們用窮舉法驗(yàn)證一下因?yàn)槲锲房梢郧懈钊魏畏桨付嫉葍r(jià)于“每個(gè)物品裝了多少比例”。如果裝A的0.5、B的1、C的0.5總體積是 (5201540)總共只裝了40的容量浪費(fèi)了10顯然還可以把更多的C裝進(jìn)來。任何沒有把容量用完的方案都可以通過多加一點(diǎn)當(dāng)前剩余里單位價(jià)值最高的物品來提升總價(jià)值所以最優(yōu)解一定是容量剛好用完的。在這個(gè)約束下每一步拿的單位價(jià)值最高的物品占比越大總價(jià)值就越高。上面這個(gè)例子里240就是最優(yōu)解。你可以試著把A換成別的物品裝法會(huì)發(fā)現(xiàn)無論如何總價(jià)值都不會(huì)超過240。3.2 代碼實(shí)現(xiàn)排序加貪心二十行搞定分?jǐn)?shù)背包的實(shí)現(xiàn)極其樸素我用Python寫一個(gè)通用版本方便你直接改成任何語言def fractional_knapsack(weights, values, capacity): # 將物品按單位價(jià)值從高到低排序 items sorted( [(values[i] / weights[i], weights[i], values[i]) for i in range(len(weights))], reverseTrue ) total_value 0.0 for unit_value, weight, value in items: if capacity 0: break if weight capacity: # 整件裝入 capacity - weight total_value value else: # 裝入一部分 fraction capacity / weight total_value value * fraction capacity 0 return total_value weights [10, 20, 30] values [60, 100, 120] capacity 50 print(fractional_knapsack(weights, values, capacity)) # 輸出 240.0這段代碼內(nèi)置了“裝不下整件就裝部分”的邏輯時(shí)間復(fù)雜度主要集中在排序上為O(n log n)遍歷是O(n)。在物品數(shù)量十萬級(jí)以內(nèi)時(shí)這個(gè)性能是近乎實(shí)時(shí)的。3.3 為什么分?jǐn)?shù)背包的貪心能被證明正確我在前面說過貪心策略不能靠“感覺正確”就草率采用分?jǐn)?shù)背包能成為教學(xué)經(jīng)典恰恰在于它的正確性可以被嚴(yán)格證明。這里的核心論據(jù)是交換論證假設(shè)某個(gè)方案不是按照單位價(jià)值排序裝的那一定存在相鄰兩件物品I和JJ的單位價(jià)值高于I卻排在I前面被先裝。如果J和I的裝入量都不為0我們保持總量不變把一部分J的裝入量換成等重量的I。因?yàn)镮的單位價(jià)值更高交換后總價(jià)值只增不減。反復(fù)進(jìn)行這種交換直到所有物品都按單位價(jià)值從高到低排列。任何最優(yōu)方案經(jīng)過有限次交換都能變?yōu)樨澬姆桨盖铱們r(jià)值不會(huì)下降反過來貪心方案就是那個(gè)“怎么交換都不會(huì)變差”的方案所以它一定是最優(yōu)的。這個(gè)證明思路值得細(xì)品——它沒有直接證明“貪心產(chǎn)生的解是唯一最優(yōu)解”而是證明“任何不是貪心的最優(yōu)解都可以被改造成貪心解且價(jià)值不變差”。這正是貪心證明中常用的形態(tài)你不需要證明貪心策略碾壓一切你只需要證明不存在任何比貪心更好的選擇。4. 0-1背包同一個(gè)背包為什么貪心突然就失靈了如果說分?jǐn)?shù)背包是貪心的主場那0-1背包就是貪心的墓地。0-1背包和分?jǐn)?shù)背包幾乎一樣唯一的差別是每個(gè)物品只能整體裝入或不裝入不能切割。就這一個(gè)約束的變化直接導(dǎo)致貪心策略崩塌。來看一個(gè)經(jīng)典反例。假設(shè)背包容量只有10有兩件物品物品A重量6價(jià)值30單位價(jià)值5物品B重量5價(jià)值25單位價(jià)值5這里兩件物品單位價(jià)值相同按排序任意選一個(gè)先裝。如果先裝A剩余容量4裝不下B總價(jià)值30如果先裝B剩余容量5裝不下A總價(jià)值25。貪心選了A拿到30?？扇绻麚Q一組數(shù)據(jù)——背包容量10物品A重量7價(jià)值42單位價(jià)值6物品B重量6價(jià)值36單位價(jià)值6物品C重量4價(jià)值20單位價(jià)值5按單位價(jià)值排序先裝A剩余容量3什么都裝不下總價(jià)值42。但最優(yōu)解是BC總重量10價(jià)值56。貪心在這里徹底翻車因?yàn)樗鼉?yōu)先選了A沒意識(shí)到“A占的重量太大擠掉了B和C組合出的更優(yōu)解”。0-1背包的問題出在哪出在物品的不可分割性。在分?jǐn)?shù)背包里拿完貴的還能拿便宜的容量永遠(yuǎn)可以被完美利用但在0-1背包里“拿某件物品”是一個(gè)布爾決策你占了容量卻不一定拿到最優(yōu)的“容量-價(jià)值性價(jià)比”。貪心只看到了“單位價(jià)值最高”卻忽略了“組合效應(yīng)”——兩件中等單位價(jià)值的物品組合可能遠(yuǎn)遠(yuǎn)勝過一件高單位價(jià)值但死重的物品。這是個(gè)很重要的認(rèn)知貪心算法對(duì)“連續(xù)資源分配”問題非常友好但面對(duì)“離散組合選擇”問題時(shí)就要格外警惕。0-1背包的每個(gè)物品都是“全有或全無”它需要的是動(dòng)態(tài)規(guī)劃——設(shè)dp[i][j]表示前i件物品在容量為j時(shí)能獲得的最大價(jià)值狀態(tài)轉(zhuǎn)移為dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])時(shí)間復(fù)雜度O(nW)。這個(gè)對(duì)比告訴你同樣是背包問題自動(dòng)判斷“能不能貪心”往往比記住算法更重要。我還想補(bǔ)充一個(gè)工程上的實(shí)用判斷法當(dāng)問題的可行解由“集合選擇”構(gòu)成并且候選之間互相排斥時(shí)貪心通常不成立當(dāng)問題的可行解由“比例分配”構(gòu)成并且候選可以無損失切分時(shí)貪心往往成立。用這個(gè)標(biāo)準(zhǔn)去套場景“從課程里選若干門每門課占用時(shí)間且算學(xué)分”是0-1背包貪心危險(xiǎn)“把有限的廣告預(yù)算分配到不同渠道渠道可以投一部分”是分?jǐn)?shù)背包貪心安全。5. 貪心算法的更多經(jīng)典場景與實(shí)現(xiàn)樣板背包問題只是貪心的一個(gè)入口掌握貪心算法還需要熟悉幾個(gè)高頻的經(jīng)典應(yīng)用。這些場景不只是面試題它們的抽象模式在真實(shí)工程中非常常見。5.1 活動(dòng)安排問題按結(jié)束時(shí)間貪才是關(guān)鍵假設(shè)你有一間會(huì)議室收到一堆活動(dòng)申請(qǐng)每個(gè)活動(dòng)有開始時(shí)間s[i]和結(jié)束時(shí)間f[i]同一時(shí)間只能安排一個(gè)活動(dòng)問最多能安排多少個(gè)活動(dòng)。很多初學(xué)者第一反應(yīng)是“按開始時(shí)間最早的優(yōu)先”或者“按持續(xù)時(shí)間最短的優(yōu)先”這兩種策略都能輕易構(gòu)造反例。正確的貪心策略是按結(jié)束時(shí)間從早到晚排序優(yōu)先選擇結(jié)束時(shí)間最早且與已選活動(dòng)不沖突的活動(dòng)。直覺是結(jié)束時(shí)間越早給后續(xù)活動(dòng)留出的時(shí)間就越多也就越可能安排進(jìn)更多活動(dòng)。這個(gè)問題的證明同樣可以用交換論證假設(shè)某個(gè)最優(yōu)解里第一個(gè)活動(dòng)不是結(jié)束時(shí)間最早的A而是另一個(gè)活動(dòng)B。因?yàn)锳的結(jié)束時(shí)間不晚于B所以把B替換成A后不會(huì)影響后續(xù)活動(dòng)的安排解仍然合法且數(shù)量相同。于是存在一個(gè)包含A的最優(yōu)解對(duì)剩余活動(dòng)遞歸同樣成立貪心就是最優(yōu)的。實(shí)際實(shí)現(xiàn)只需要一次排序加一次線性掃描def max_activities(activities): # activities: [(start, end), ...] activities.sort(keylambda x: x[1]) # 按結(jié)束時(shí)間排序 count 0 last_end -1 for start, end in activities: if start last_end: count 1 last_end end return count這個(gè)場景映射到現(xiàn)實(shí)就是會(huì)議室預(yù)訂、單機(jī)任務(wù)調(diào)度、帶寬分配等凡是“一個(gè)資源、多個(gè)帶起止時(shí)間的請(qǐng)求、最大化吞吐量”的問題都可以套這個(gè)模板。5.2 哈夫曼編碼頻率越低越要靠近葉子底部數(shù)據(jù)壓縮里的哈夫曼編碼也是貪心的典型代表。它的目標(biāo)是用最短的平均編碼長度來無損表示一批字符做法是每次從字符集合中挑出出現(xiàn)頻率最低的兩個(gè)節(jié)點(diǎn)合并成一個(gè)新節(jié)點(diǎn)新節(jié)點(diǎn)的權(quán)重是二者之和并把合并后的節(jié)點(diǎn)放回集合重復(fù)到只剩一個(gè)根節(jié)點(diǎn)為止。這本質(zhì)上是一種“自底向上建樹”的貪心——總是在當(dāng)前狀態(tài)下找代價(jià)最小的局部合并。哈夫曼編碼的正確性證明思路是在任意最優(yōu)前綴編碼樹中頻率最低的兩個(gè)字符一定出現(xiàn)在最深層且互為兄弟。這個(gè)論斷可以用交換論證證明如果頻率最低的兩個(gè)字符不在最底層把一個(gè)更深層的字符和它們中的一個(gè)交換總編碼長度會(huì)下降從而矛盾。所以貪心選擇每次合并最低頻的兩項(xiàng)并不會(huì)丟失最優(yōu)解。這個(gè)證明我在面試中遇到過不止一次建議你把它的邏輯理順而不是只背“每次選最小的兩個(gè)”。實(shí)現(xiàn)時(shí)通常用小頂堆優(yōu)先隊(duì)列來維護(hù)當(dāng)前所有節(jié)點(diǎn)的權(quán)重每次彈出兩個(gè)最小的合并后壓回。復(fù)雜度為O(n log n)是構(gòu)建最優(yōu)前綴編碼的標(biāo)準(zhǔn)方案。5.3 最小生成樹Kruskal和Prim都是貪心圖論里的最小生成樹是貪心的另一個(gè)大殺器。Kruskal算法的策略是把邊按權(quán)重從小到大排序從最小的邊開始只要這條邊連接的兩個(gè)頂點(diǎn)尚未連通就加入生成樹。Prim算法則是從一個(gè)起點(diǎn)出發(fā)每次都挑當(dāng)前已選頂點(diǎn)集合到未選頂點(diǎn)集合之間的最小權(quán)邊擴(kuò)展。這兩個(gè)算法能成功的關(guān)鍵在于圖論中的“切割性質(zhì)”如果一條邊是橫跨某個(gè)割的最小權(quán)邊那它一定在某個(gè)最小生成樹中。這個(gè)性質(zhì)保證了每一步貪心選擇“不會(huì)把最優(yōu)解排除在外”這正是前面說的貪心選擇性質(zhì)。Kruskal需要配合并查集來判斷連通性Prim可以用優(yōu)先隊(duì)列來快速取最小邊兩者在稀疏圖和稠密圖上各有優(yōu)勢(shì)。工程網(wǎng)絡(luò)設(shè)計(jì)、電路布線、集群拓?fù)鋬?yōu)化里這兩個(gè)算法都是骨灰級(jí)工具。5.4 Dijkstra最短路徑每次都只確認(rèn)眼前最近的一點(diǎn)單源最短路徑的Dijkstra算法同樣內(nèi)置貪心思想。它的策略是維護(hù)一個(gè)“已確定最短路徑頂點(diǎn)集合”每次都從未確定的頂點(diǎn)里挑一個(gè)與源點(diǎn)距離最近的點(diǎn)加入集合并松弛它所有出邊。這個(gè)“最近”是當(dāng)前已算出的暫定距離貪心在每一步固定一個(gè)頂點(diǎn)的最終最短距離。Dijkstra能這么做的前提是邊的權(quán)重非負(fù)。因?yàn)榉秦?fù)權(quán)重保證“當(dāng)前距離最小的未處理頂點(diǎn)”不可能再被其他路徑縮短——所有能到達(dá)它的路徑至少已經(jīng)經(jīng)過一個(gè)未處理頂點(diǎn)而這個(gè)未處理頂點(diǎn)本身距離就不小于它加上非負(fù)邊權(quán)只會(huì)更遠(yuǎn)。這個(gè)推理一旦遇到負(fù)權(quán)邊就失效了所以Dijkstra不能處理負(fù)權(quán)圖得用Bellman-Ford。這也是一個(gè)理解“貪心策略對(duì)問題條件極其敏感”的好例子。這些經(jīng)典案例放在一起看你會(huì)發(fā)現(xiàn)一個(gè)共性貪心算法不是一種“統(tǒng)一的算法”而是一種“策略范式”。每個(gè)具體問題都要單獨(dú)設(shè)計(jì)貪心規(guī)則、單獨(dú)證明規(guī)則的安全性不同問題的“局部最優(yōu)”定義可能完全不同——活動(dòng)安排看結(jié)束時(shí)間哈夫曼看字符頻率Kruskal看邊權(quán)。這種靈活度既是貪心的魅力也是學(xué)習(xí)時(shí)最容易困惑的地方。6. 如何快速判斷一個(gè)題目能不能用貪心解學(xué)完經(jīng)典案例之后你肯定會(huì)遇到一個(gè)現(xiàn)實(shí)問題新題目來了我怎么知道它能不能貪心在工作或面試中你不可能每次都把教材翻一遍。這里我分享一套自己的快速判斷流程不一定絕對(duì)嚴(yán)密但能大幅降低試錯(cuò)成本。第一步看問題是否具備最優(yōu)子結(jié)構(gòu)。把問題按“先做一個(gè)選擇然后處理剩下部分”的方式切分問自己如果剩下部分不是最優(yōu)解整個(gè)問題還能是最優(yōu)解嗎大多數(shù)優(yōu)化類問題都滿足這個(gè)條件不滿足時(shí)問題往往無法用動(dòng)態(tài)規(guī)劃或貪心這類“分而治之”的框架解決需要考慮別的手段。第二步試著構(gòu)造反例。無論你想出了什么貪心規(guī)則都先逼自己嘗試構(gòu)造一個(gè)反例證明“這個(gè)規(guī)則會(huì)翻車”。如果你能在幾分鐘內(nèi)構(gòu)造出反例說明規(guī)則有問題或者這個(gè)問題壓根不適合貪心。如果你試了很多組數(shù)據(jù)都沒找到反例再把題目往已知的經(jīng)典模型上靠——它會(huì)不會(huì)本質(zhì)上是分?jǐn)?shù)背包、活動(dòng)安排、最小生成樹或者Dijkstra中的某一種第三步如果無法確定優(yōu)先嘗試動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃幾乎可以覆蓋所有滿足最優(yōu)子結(jié)構(gòu)的問題代價(jià)只是更高的時(shí)間和空間復(fù)雜度。寫一個(gè)動(dòng)態(tài)規(guī)劃版本作為baseline再寫貪心版本用隨機(jī)生成的測(cè)試數(shù)據(jù)對(duì)拍驗(yàn)證正確性。這也是我強(qiáng)烈建議算法初學(xué)者養(yǎng)成的習(xí)慣——對(duì)拍是驗(yàn)證算法正確性的最實(shí)用方法比任何紙面證明都直接。第四步如果你的貪心版本在大規(guī)模隨機(jī)數(shù)據(jù)上依然與動(dòng)態(tài)規(guī)劃結(jié)果一致它有極大概率是正確的。這時(shí)候再嘗試用交換論證或數(shù)學(xué)歸納法補(bǔ)一個(gè)正式證明。很多人把證明放到最后一步會(huì)覺得很痛苦但當(dāng)你已經(jīng)對(duì)拍過數(shù)千組數(shù)據(jù)后證明思路往往也會(huì)在測(cè)試中自然浮現(xiàn)。需要強(qiáng)調(diào)的是這個(gè)流程并非數(shù)學(xué)上完備的判定算法但它在工程實(shí)踐中極其有效。真隨機(jī)對(duì)拍能過濾掉絕大多數(shù)錯(cuò)誤貪心策略而剩下的那些能通過對(duì)拍的“候選貪心”大多數(shù)時(shí)候確實(shí)會(huì)帶著你找到正確的證明路徑。7. 貪心雖好用但這些坑一定要繞開最后按老規(guī)矩把我這些年踩過的坑和帶學(xué)員時(shí)經(jīng)常看到的問題集中分享一下。第一個(gè)坑用貪心直接套0-1背包。這個(gè)問題我在上面專門分析過但現(xiàn)實(shí)里它仍然以各種偽裝出現(xiàn)。比如“給你一筆預(yù)算從若干項(xiàng)目中選幾個(gè)做每個(gè)項(xiàng)目有成本與收益怎么選收益最大”——這就是0-1背包不能用“先做性價(jià)比最高的項(xiàng)目”來解。應(yīng)對(duì)方案是要么改用動(dòng)態(tài)規(guī)劃要么如果項(xiàng)目可以部分開展投一部分錢獲得對(duì)應(yīng)比例收益才可以用貪心。區(qū)分清楚“能不能切分”永遠(yuǎn)是第一步。第二個(gè)坑Kruskal算法里忘了處理并查集的路徑壓縮和按秩合并。有些人在小圖上跑得通數(shù)據(jù)一多就超時(shí)不是貪心策略錯(cuò)而是并查集實(shí)現(xiàn)太粗糙。路徑壓縮幾乎是免費(fèi)的一定要加按秩合并不是必須但建議加上極端情況下能顯著降低常數(shù)。寫算法題時(shí)貪心部分往往不是瓶頸輔助數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)效率才是。第三個(gè)坑哈夫曼編碼建樹時(shí)把輸入序列當(dāng)成已排序的忽略了合并產(chǎn)生的新節(jié)點(diǎn)需要重新參與比較的過程。標(biāo)準(zhǔn)的實(shí)現(xiàn)應(yīng)該用優(yōu)先隊(duì)列否則每次取最小都要掃描一遍復(fù)雜度退化成O(n2)。我見過有人因?yàn)椤白址淮蟆本屯祽兄钡教幚砩先f字符的語料時(shí)才被性能打臉。第四個(gè)坑貪心策略在競賽里碰壁后直接否定所有貪心思路。這個(gè)心理陷阱其實(shí)最隱蔽。貪心算法本身沒有錯(cuò)錯(cuò)的是“這個(gè)問題的這個(gè)貪心規(guī)則”不對(duì)。同一個(gè)背包問題分?jǐn)?shù)背包貪心對(duì)、0-1背包貪心錯(cuò)同一個(gè)圖論問題非負(fù)權(quán)最短路Dijkstra對(duì)、帶負(fù)權(quán)最短路Dijkstra錯(cuò)。不要把問題簡單歸因于“貪心不靠譜”而是要細(xì)化到“當(dāng)前這個(gè)決策規(guī)則為什么不能成立”。還有一個(gè)實(shí)戰(zhàn)習(xí)慣值得培養(yǎng)每當(dāng)你設(shè)計(jì)出一個(gè)貪心規(guī)則立刻寫下它的不變量也就是“在每一步?jīng)Q策之后當(dāng)前已選集合一定不劣于任何其他相同規(guī)模的集合”。這個(gè)不變量如果能在整個(gè)算法執(zhí)行過程中始終保持那貪心策略幾乎必然正確。寫不出來的話你的貪心大概率有問題。以我個(gè)人經(jīng)驗(yàn)來看貪心算法的學(xué)習(xí)路徑應(yīng)該是一條“從直覺到證明再到自動(dòng)化判斷”的曲線。一開始誰都能說出“每一步選最好的”這句話但真正拉開差距的是你能不能在五分鐘后給出讓人信服的正確性論證或者高效地構(gòu)造出反例來否定一個(gè)貌似合理實(shí)則錯(cuò)誤的策略。這兩種能力都不是天生的多寫證明、多對(duì)拍、多積累經(jīng)典模型的變形慢慢就會(huì)形成肌肉記憶。希望這篇文章能幫你在貪心算法的地基上站穩(wěn)后面不管是啃動(dòng)態(tài)規(guī)劃還是面對(duì)更復(fù)雜的優(yōu)化問題都會(huì)走得順利很多。