C++貪心算法

「貪心算法 greedy algorithm」是一種常見的解決優(yōu)化問題的算法，其基本思想是在問題的每個(gè)決策階段，都選擇當(dāng)前看起來最優(yōu)的選擇，即貪心地做出局部最優(yōu)的決策，以期望獲得全局最優(yōu)解。貪心算法簡潔且高效，在許多實(shí)際問題中都有著廣泛的應(yīng)用。

貪心算法和動(dòng)態(tài)規(guī)劃都常用于解決優(yōu)化問題。它們之間存在一些相似之處，比如都依賴最優(yōu)子結(jié)構(gòu)性質(zhì)，但工作原理是不同的。

• 動(dòng)態(tài)規(guī)劃會根據(jù)之前階段的所有決策來考慮當(dāng)前決策，并使用過去子問題的解來構(gòu)建當(dāng)前子問題的解。
• 貪心算法不會重新考慮過去的決策，而是一路向前地進(jìn)行貪心選擇，不斷縮小問題范圍，直至問題被解決。

我們先通過例題“零錢兌換”了解貪心算法的工作原理。這道題已經(jīng)在動(dòng)態(tài)規(guī)劃章節(jié)中介紹過，相信你對它并不陌生。

本題的貪心策略如圖 15-1 所示。給定目標(biāo)金額，我們貪心地選擇不大于且最接近它的硬幣，不斷循環(huán)該步驟，直至湊出目標(biāo)金額為止。

圖 15-1   零錢兌換的貪心策略

實(shí)現(xiàn)代碼如下所示。你可能會不由地發(fā)出感嘆：So Clean ！貪心算法僅用十行代碼就解決了零錢兌換問題。

coin_change_greedy.cpp

/* 零錢兌換：貪心 */
int coinChangeGreedy(vector<int> &coins, int amt) {
    // 假設(shè) coins 列表有序
    int i = coins.size() - 1;
    int count = 0;
    // 循環(huán)進(jìn)行貪心選擇，直到無剩余金額
    while (amt > 0) {
        // 找到小于且最接近剩余金額的硬幣
        while (i > 0 && coins[i] > amt) {
            i--;
        }
        // 選擇 coins[i]
        amt -= coins[i];
        count++;
    }
    // 若未找到可行方案，則返回 -1
    return amt == 0 ? count : -1;
}

貪心優(yōu)點(diǎn)與局限性

貪心算法不僅操作直接、實(shí)現(xiàn)簡單，而且通常效率也很高。在以上代碼中，記硬幣最小面值為 $min(coins)$ ，則貪心選擇最多循環(huán) $amt/min(coins)$ 次，時(shí)間復(fù)雜度為 $O(amt/min(coins))$ 。這比動(dòng)態(tài)規(guī)劃解法的時(shí)間復(fù)雜度 $O(n\times amt)$ 提升了一個(gè)數(shù)量級。

然而，對于某些硬幣面值組合，貪心算法并不能找到最優(yōu)解。圖 15-2 給出了兩個(gè)示例。

• 正例 $coins=[1,5,10,20,50,100]$：在該硬幣組合下，給定任意 $amt$ ，貪心算法都可以找出最優(yōu)解。
• 反例 $coins=[1,20,50]$：假設(shè) $amt=60$ ，貪心算法只能找到 $50+1\times 10$ 的兌換組合，共計(jì) $11$ 枚硬幣，但動(dòng)態(tài)規(guī)劃可以找到最優(yōu)解 $20+20+20$ ，僅需 $3$ 枚硬幣。
• 反例 $coins=[1,49,50]$：假設(shè) $amt=98$ ，貪心算法只能找到 $50+1\times 48$ 的兌換組合，共計(jì) $49$ 枚硬幣，但動(dòng)態(tài)規(guī)劃可以找到最優(yōu)解 $49+49$ ，僅需 $2$ 枚硬幣。

圖 15-2   貪心無法找出最優(yōu)解的示例

也就是說，對于零錢兌換問題，貪心算法無法保證找到全局最優(yōu)解，并且有可能找到非常差的解。它更適合用動(dòng)態(tài)規(guī)劃解決。

一般情況下，貪心算法適用于以下兩類問題。

1. 可以保證找到最優(yōu)解：貪心算法在這種情況下往往是最優(yōu)選擇，因?yàn)樗然厮?、?dòng)態(tài)規(guī)劃更高效。
2. 可以找到近似最優(yōu)解：貪心算法在這種情況下也是可用的。對于很多復(fù)雜問題來說，尋找全局最優(yōu)解是非常困難的，能以較高效率找到次優(yōu)解也是非常不錯(cuò)的。

貪心算法特性

那么問題來了，什么樣的問題適合用貪心算法求解呢？或者說，貪心算法在什么情況下可以保證找到最優(yōu)解？

相較于動(dòng)態(tài)規(guī)劃，貪心算法的使用條件更加苛刻，其主要關(guān)注問題的兩個(gè)性質(zhì)。

• 貪心選擇性質(zhì)：只有當(dāng)局部最優(yōu)選擇始終可以導(dǎo)致全局最優(yōu)解時(shí)，貪心算法才能保證得到最優(yōu)解。
• 最優(yōu)子結(jié)構(gòu)：原問題的最優(yōu)解包含子問題的最優(yōu)解。

最優(yōu)子結(jié)構(gòu)已經(jīng)在動(dòng)態(tài)規(guī)劃章節(jié)中介紹過，不再贅述。值得注意的是，一些問題的最優(yōu)子結(jié)構(gòu)并不明顯，但仍然可使用貪心算法解決。

我們主要探究貪心選擇性質(zhì)的判斷方法。雖然它的描述看上去比較簡單，但實(shí)際上對于許多問題，證明貪心選擇性質(zhì)不是一件易事。

例如零錢兌換問題，我們雖然能夠容易地舉出反例，對貪心選擇性質(zhì)進(jìn)行證偽，但證實(shí)的難度較大。如果問：滿足什么條件的硬幣組合可以使用貪心算法求解？我們往往只能憑借直覺或舉例子來給出一個(gè)模棱兩可的答案，而難以給出嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)證明。

貪心解題步驟

貪心問題的解決流程大體可分為以下三步。

1. 問題分析：梳理與理解問題特性，包括狀態(tài)定義、優(yōu)化目標(biāo)和約束條件等。這一步在回溯和動(dòng)態(tài)規(guī)劃中都有涉及。
2. 確定貪心策略：確定如何在每一步中做出貪心選擇。這個(gè)策略能夠在每一步減小問題的規(guī)模，并最終能解決整個(gè)問題。
3. 正確性證明：通常需要證明問題具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。這個(gè)步驟可能需要使用到數(shù)學(xué)證明，例如歸納法或反證法等。

確定貪心策略是求解問題的核心步驟，但實(shí)施起來可能并不容易，主要包含以下原因。

• 不同問題的貪心策略的差異較大。對于許多問題來說，貪心策略都比較淺顯，我們通過一些大概的思考與嘗試就能得出。而對于一些復(fù)雜問題，貪心策略可能非常隱蔽，這種情況就非常考驗(yàn)個(gè)人的解題經(jīng)驗(yàn)與算法能力了。
• 某些貪心策略具有較強(qiáng)的迷惑性。當(dāng)我們滿懷信心設(shè)計(jì)好貪心策略，寫出解題代碼并提交運(yùn)行，很可能發(fā)現(xiàn)部分測試樣例無法通過。這是因?yàn)樵O(shè)計(jì)的貪心策略只是“部分正確”的，上文介紹的零錢兌換就是個(gè)典型案例。

為了保證正確性，我們應(yīng)該對貪心策略進(jìn)行嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)證明，通常需要用到反證法或數(shù)學(xué)歸納法。

然而，正確性證明也很可能不是一件易事。如若沒有頭緒，我們通常會選擇面向測試用例進(jìn)行 Debug ，一步步修改與驗(yàn)證貪心策略。

貪心典型例題

貪心算法常常應(yīng)用在滿足貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)的優(yōu)化問題中，以下列舉了一些典型的貪心算法問題。

• 硬幣找零問題：在某些硬幣組合下，貪心算法總是可以得到最優(yōu)解。
• 區(qū)間調(diào)度問題：假設(shè)你有一些任務(wù)，每個(gè)任務(wù)在一段時(shí)間內(nèi)進(jìn)行，你的目標(biāo)是完成盡可能多的任務(wù)。如果每次都選擇結(jié)束時(shí)間最早的任務(wù)，那么貪心算法就可以得到最優(yōu)解。
• 分?jǐn)?shù)背包問題：給定一組物品和一個(gè)載重量，你的目標(biāo)是選擇一組物品，使得總重量不超過載重量，且總價(jià)值最大。如果每次都選擇性價(jià)比最高（價(jià)值 / 重量）的物品，那么貪心算法在一些情況下可以得到最優(yōu)解。
• 股票買賣問題：給定一組股票的歷史價(jià)格，你可以進(jìn)行多次買賣，但如果你已經(jīng)持有股票，那么在賣出之前不能再買，目標(biāo)是獲取最大利潤。
• 霍夫曼編碼：霍夫曼編碼是一種用于無損數(shù)據(jù)壓縮的貪心算法。通過構(gòu)建霍夫曼樹，每次選擇出現(xiàn)頻率最小的兩個(gè)節(jié)點(diǎn)合并，最后得到的霍夫曼樹的帶權(quán)路徑長度（即編碼長度）最小。
• Dijkstra 算法：它是一種解決給定源頂點(diǎn)到其余各頂點(diǎn)的最短路徑問題的貪心算法。