演算法筆記系列 — Greedy Algorithm 貪婪演算法
貪婪演算法（Greedy Algorithm）是一種非常常見且直觀的方法，顧名思義，核心思想是通過每一步都做出「當前看起來最佳的選擇」，以期望最終達到全局最優解。然而，貪婪演算法並非總能保證找到全局最優解，有時候往往因為當下選擇了當前最佳的選擇，反而整體來多並不是最好的解法，但在某些特定問題上，它確實提供了一種高效的解法。
什麼是 Greedy？
基本原理
貪婪演算法的基本思想是：在每一步驟中，選擇當前看來最好的選擇，而不考慮全局的後果，也就是說，貪婪演算法在處理問題時，不會回溯或重做選擇，它僅僅是基於當前狀態，做出局部最優的決策。
這種方法在某些情況下非常有效，特別是在解決那些具有 貪婪選擇性質 和 最優子結構 的問題時：
- 貪婪選擇性質：可以通過當前局部的最佳選擇，導致全局最優解。
- 最優子結構：一個問題的最優解包含其子問題的最優解。
適用的問題
由於只考慮局部最佳解，而不總是能得到全局最優解，所以貪婪演算法並不適用於所有問題，以下幾種問題類型適用於貪婪演算法：
- 活動選擇問題：選擇一組活動，使得它們互不衝突且數量最多。這個問題可以通過每次選擇最早結束的活動來解決。
- 找零問題：假設你有無限量的各種面額的硬幣，問怎麼用最少數量的硬幣來找零。這個問題通常可以用貪心算法來解決，前提是硬幣的面額設計符合特定條件（如面額是 1, 5, 10, 25）。
- 找最大利潤問題：可以進行多次交易（買入和賣出），找出最大利潤，透過每次都選擇當天最大利潤來解決。
- 最短路徑問題（Dijkstra 演算法）：在加權圖中尋找從一個節點到其他節點的最短路徑。Dijkstra 演算法是一個貪婪演算法的經典例子，它每次選擇當前最短的路徑，並逐步構建出整個最短路徑樹。
延伸閱讀：
實際應用例子
我們實際拿一題 leetcode 的題目，使用貪婪演算法的概念來嘗試解題。
122. Best Time to Buy and Sell Stock II
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
題意
題目：給定一個整數數組 prices，其中 prices[i] 表示第 i 天的股票價格。你可以進行多次交易（買入和賣出）。每次交易必須在前一次交易的賣出之後進行買入。你可以在任何一天買入或賣出，但每次買入後必須等到下次賣出。
要求：返回你能夠獲得的最大利潤。
解題思考
對於這個問題，貪婪演算法是最合適的解法，因為我們希望最大化總收益，最簡單的方式是每當價格上升時就進行買入和賣出。簡單來說，我們可以在每次價格上升的時候，將其視為一個交易機會。
因此，每當價格上升時進行交易：如果 prices[i] > prices[i-1]，那麼這段時間內的收益就是 prices[i] - prices[i-1]。
function maxProfit(prices) {
let profit = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}當然，這題我們也可以使用動態規劃來解題，透過確定每一天的最佳交易策略，以最大化最終的總收益，也就是定義子問題來逐步求解整個問題。
關於這題更詳細的討論，可以看這篇延伸閱讀：
Greedy Algorithm 的限制
貪婪演算法的主要的限制，在於它不適合所有類型的問題，對於那些局部最優解不能導致全局最優解的情況，貪婪演算法可能會得到不是最佳解，甚至錯誤的解答。
舉個例子，我們可以直接來看看 House Robber 這題：
198. House Robber
https://leetcode.com/problems/house-robber/
題意
你是一名專業的強盜，計劃沿著一條街道搶劫房子。每個房子裡都有一定數量的現金存放，但唯一限制你搶劫每個房子的因素是相鄰的房子之間有連接的安全系統。如果在同一個晚上闖入兩個相鄰的房子，安全系統將自動聯繫警方。
給定一個整數數組 nums，表示每個房子裡的金錢數量，請返回你今晚在不驚動警方的情況下，能搶到的最多金額。
問題解析
這題的目標就是要從拿到的 nums 中，取得符合條件的最大值總和，而條件就是不能取相鄰的值，其實就是一種取得子陣列和的問題，也是經典的動態規劃問題之一。
var rob = function(nums) {
const len = nums.length;
if (len === 1) return nums[0]
// init dp array
const dp = new Array(len);
// default value
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
// finish de array
for (let i = 2; i < len; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[len -1];
};關於這題更多詳細討論可以看這篇：
使用 Greedy（貪婪演算法）來解這題並不適合，原因在於問題的結構使得局部最佳解並不總是能導致全局最佳解。
這題目要求的是在不搶劫相鄰房子的情況下，找到能搶到的最大金額。因為每次選擇都會影響後續的選擇，因此每次選擇當前最大金額的房子並不能保證全局最優解。例如，搶劫了當前最大的房子後，你可能會錯過後面一組更優的選擇。
Greedy 的思考流程
貪婪演算法的核心思想是每一步都選擇當前看起來最優的選擇，希望通過一系列的局部最優選擇達到全局最優。所以在這個問題中，你可能會想到每次都搶劫當前金額最大的房子，並跳過相鄰的房子。
function rob(nums) {
let n = nums.length;
if (n === 0) return 0;
if (n === 1) return nums[0];
let i = 0;
let totalRobbed = 0;
while (i < n) {
// 假設當前選擇當前可偷到的最大金額
if (i == n - 1 || nums[i] > nums[i + 1]) {
totalRobbed += nums[i];
i += 2; // 跳過下一個房子
} else {
i += 1; // 移動到下一個房子
}
}
return totalRobbed;
}
產生的問題
對於 nums = [1, 2, 3, 1]，Greedy 策略可能會先選擇 3（第 3 個房子），然後選擇 1（第 1 個房子），總計偷取 4，這會剛好是正確答案，但我們再來看下面這個例子。
假設有這樣一個房子數組：[2, 7, 9, 3, 1]。
如果按照 Greedy 的思路，第一次選擇最大的值 9，那麼你就會跳過相鄰的 7 和 3，接下來可能選擇 1。這樣搶劫到的總金額是 9 + 1 = 10。
但是，如果選擇搶劫 7 和 3，總金額就是 7 + 3 = 10，這在這種情況下是相同的。但更優的選擇應該是搶劫 2, 9, 1，總金額為 2 + 9 + 1 = 12。
這意味著貪婪演算法容易在選擇當前最優時忽略未來的可能性，導致無法得到全局最優解。
如果你覺得這篇文章對你有幫助，歡迎買杯咖啡贊助 ☕️ 謝謝
