本文同步更新於個人網站中,有更好的排版和程式碼區塊 highlighting 支援。
貪婪演算法(Greedy Algorithm)是一種在每一步選擇中都採取在目前狀態下最好或最佳(即最有利)的選擇,從而希望獲得全體最好或最佳解的演算法。
貪婪演算法和動態規劃都常用來解決最佳化問題。它們之間存在一些相似處,例如都依賴於最佳子結構,但工作原理不同。
我們拿之前看過的 coin change 來舉例,有 n
種硬幣 coins
,第 i
種硬幣的面額為 coins[i - 1]
,每種硬幣都能重複選擇,問能夠湊出目標值 amount
的最少硬幣數量。
用 greedy 策略來解這個問題就是我們每次都貪心地選擇不大於 amount
且最接近它的硬幣,然後將 amount
減去該硬幣的面額,不斷地重複這兩個步驟,直到 amount
減為 0,這時我們就找到了最少硬幣數量。如下所示:
amount | coins | coins used |
---|---|---|
11 | [1, 2, 5] | 5 |
6 | [1, 2, 5] | 5 |
1 | [1, 2, 5] | 1 |
用程式碼來表示就是:
function coinChangeGreedy(coins, amount) {
// 假設 coins 陣列已經排序過
let count = 0;
let i = coins.length - 1;
// 進行 greedy 選擇,直到 amount 為 0
while (amount > 0) {
// 如果當前的 coin 大於 amount,則跳過
if (coins[i] > amount) {
i--;
continue;
}
// 進行選擇
amount -= coins[i];
count++;
}
return amount === 0 ? count : -1;
}
貪婪演算法的操作很直觀,實作簡單且通常效率也不錯。在剛才的程式碼中,設硬幣最小面額為 min(coins)
,則 greedy 選擇最多跑 amount / min(coins)
次迴圈,時間複雜度為 。相對動態規劃的時間複雜度 來說,提升了一個數量級。
但是對於某些硬幣面額組成,greedy 無法找到最佳解。下面舉幾個例子來說明:
coins = [1, 5, 10, 20, 50, 100]
:在這個硬幣組合下,給定任意 amount
都能透過 greedy 找到最佳解。coins = [1, 3, 4]
:假設 amount = 6
,greedy 會選擇 4 + 1 + 1
得出 3 枚硬幣的解,但是我們透過動態規劃可以找到最佳解 3 + 3
的 2 枚硬幣。coins = [1, 20, 50]
:假設 amount = 60
,greedy 會選擇 50 + 1 * 10
得出 11 枚硬幣的解,但是我們透過動態規劃可以找到最佳解 20 * 3
的 3 枚硬幣。也就是說對於 coin change 問題,greedy 無法保證找到全局最佳解,而且還有可能找到一個非常差的解,因此它更適合使用動態規劃來解決。
一般情況下,greedy 適用於下面兩類問題:
那麼隨之而來的問題是,什麼樣的問題適合用貪婪演算法來解決呢?或者說,貪婪演算法在什麼情況下可以保證找到最佳解呢?
相比動態規劃,greedy 的使用條件更加苛刻,主要關注問題的兩個性質:
最佳子結構我們在介紹動態規劃時提過了,這裡主要說一下 greedy choice 的判斷方法。雖然描述上看起來比較簡單,但實際上對於許多問題來說,證明 greedy choice property 並不容易。
例如 coin change 問題,我們很容易就可以找出反例,但是證明正面例子難度就比較大了。如果要問:滿足什麼條件的硬幣組合可以使用 greedy 來求解?我們往往只能憑藉感覺或舉幾個例子來給出一個模稜兩可的答案,難以給出嚴謹的數學證明。
greedy 問題的解題流程大致分為三步:
確定 greedy 策略是解題的核心步驟,但實施起來可能並不容易,因為我們常常會被一些策略給迷惑,誤以為它是最佳策略,例如前面的 coin change,然後在實作後發現無法通過部分測試案例,這是因為設計出來的貪婪策略只是“部分正確”的。
因此,我們在確定 greedy 策略後,還需要進行正確性證明,確保該策略是正確的。然而要證明正確性也可能不是一件易事,如果完全沒有頭緒,可以先嘗試用反證法,假設該策略不是最佳策略,然後找出反例,如果找不出反例,那麼該策略可能就是最佳策略了。
最後讓我們來看一題 greedy 的經典題目,分數背包問題(Fractional Knapsack Problem)。
分數背包問題和先前的 0/1 背包問題很相似,但是有一點不同,就是物品可以分割,也就是說我們可以選擇物品的一部分,而不一定是全部。我們簡單用一個例子來比較一下兩者的區別:
物品 | weight | value |
---|---|---|
1 | 2 | 3 |
2 | 3 | 4 |
3 | 4 | 5 |
在 0/1 背包問題中,如果背包的承重只有 6,只能選擇物品 1 和物品 3,最大價值為 8。
分數背包問題中允許我們只選擇物品的一部分,我們可以對物品進行任意分割,然後按照重量比例來計算價值。因此,我們可以先計算出每個物品的單位重量價值,然後按照單位重量價值從大到小排序,依次選擇物品,直到背包裝滿為止。
物品 | weight | value | unit value |
---|---|---|---|
1 | 2 | 3 | 1.5 |
2 | 3 | 4 | 1.33 |
3 | 4 | 5 | 1.25 |
我們可以選擇物品 1 和物品 2,還有 25% 的物品 3,最大價值為 8.25。
要最大化背包內物品總價值,本質上是要最大化單位重量下的物品價值(白話點就是 CP 值最高),於是我們的 greedy 策略就是價值與重量的比值最高的物品,優先放進背包。
解題流程就會是:將物品按照單位價值從高到低排序 --> 遍歷所有物品,每次都貪婪地選擇單位價值最高的物品 --> 如果背包容量不足,則將目前物品的一部分放入背包,直到背包裝滿為止。
function fractionalKnapsack(capacity, weights, values) {
const list = [];
for (let i = 0; i < weights.length; i++) {
list.push({
num: i + 1,
weight: weights[i],
value: values[i],
ratio: values[i] / weights[i],
});
}
list.sort((a, b) => b.ratio - a.ratio);
const selects = [];
let totalValue = 0;
for (let i = 0; i < list.length; i++) {
let item = list[i];
if (item.weight <= capacity) {
selects.push({
num: item.num,
weight: item.weight,
value: item.value,
ratio: 1,
});
totalValue += item.value;
capacity -= item.weight;
} else if (capacity > 0) {
const ratio = capacity / item.weight;
selects.push({
num: item.num,
weight: item.weight * ratio,
value: item.value * ratio,
ratio,
});
totalValue += item.value * ratio;
capacity -= item.weight * ratio;
break;
} else if (capacity <= 0) {
break;
}
}
return totalValue;
}
最壞情況下,我們會需要遍歷整個物品列表,因此時間複雜度為 。
採用反證法,假設物品 x 是單位重量價值最高的物品,使用某種演算法求得最大價值為 res
,但該解中不包含物品 x。
現在我們從背包中拿出單位重量的任意物品,替換成單位重量的物品 x。由於物品 x 單位重量價值最高,因此替換後的解 res'
會比 res
更大,這與 res
是最大解矛盾,因此假設不成立,得證物品 x 必定在最大解中。
總是用當下單位價值最高的物品填滿背包,最後沒有留下任何空隙。每一份背包空間,都是最有價值的物品,就算是交換物品也無法增加總價值。因此,我們的 greedy 策略是正確的。
貪婪演算法是一種求解最佳化問題的策略,其核心思想是在每一步都做出當前看似最好的選擇,希望這樣最終能達到全局最優解。然而,貪婪演算法並不是萬能的。與動態規劃相比,它有其明顯的優缺點。
優點:
缺點: