Day26. 貪心算法(Greedy Algorithm)

15th鐵人賽

雜食性的貓

2023-10-11 08:29:26

272 瀏覽

分享至

貪心算法概念

有人稱呼為貪心、有人稱呼為貪婪，反正聽得懂就可以。
貪心算法其實是一個相對抽象的概念，也可以一言以蔽之。
「當能夠採取選擇的時候，每步都採取當下的最佳選擇，期望藉由持續局部的最佳選擇，來達成全局的最佳選擇」
這就是貪心的核心思維，活在當下。
貪心的思維其實無所不在，在很多題目沒特別說，但只要有用到這個概念，都可以跟貪心扯上關係。
(如 Kruskal / Prim 的由小開始處理都有類似的概念，對邊貪心和對節點貪心)

那貪心算法中最困難的地方其實也包含在那句話裡了，「最佳選擇」，如何選出最佳選擇就是貪心問題最難的地方。
必須先定義「最佳」是什麼。
貪心算法的缺點是它也不是萬能的，應該說很多情況它都不能，只是它都能拿出兜兜看，幾個案例都兜上了，邊界確認也沒問題了，那就大膽貪心。
貪心算法的缺點在於它太過注重當下選擇，對全局的顧慮不夠，導致藉由貪心得出的結果，很多時候不是最佳解，也就沒辦法用貪心。

貪心問題舉例

貪心的全局最佳一般就是題目的命題，讓我們拿一個簡單的題目來分析。

Lemonade Change

典型的找零問題。
你是一個小販，賣一罐 5$ 的檸檬水，來買的人只會付 5, 10, 20 面額的錢，一開始你沒有錢的情況下，你能夠找每個人剛好的錢嗎？

對於這題，全局最佳就是每個人需要零錢的時候都夠找。
局部最佳是什麼？如果我現在有很多錢，我要挑哪種錢來找零？
概念是因為 10 塊不能取代 5 塊，但 5 塊可以取代 10 塊，20 塊在這個題目的概念裡是一個對完成找零的動作沒有幫助的數值。
因為上面提到的可取代性，所以我們決定能找 10 塊優先找 10 塊(不會有找 20 塊的情況)，只能找 5 塊的時後才找 5 塊，這樣能保證我們在需要 5 塊的時候是有最多 5 塊的狀態。
然後劃分可能狀況，可能狀況只有三種，來買的人付 5, 10, 20 塊，針對這三種基於上面邏輯去寫能不能找零和 5 塊 10 塊增加的狀況。
程式碼如下。

public class Solution {
    public bool LemonadeChange(int[] bills) {
        var bill10 = 0;
        var bill5 = 0;
        for(var i = 0; i < bills.Length ; i++){
            if(bills[i] == 5){
                bill5++;
            }
            else if(bills[i] == 10){
                bill5--;
                bill10++;
            }
            else if(bills[i] == 20){
                if(bill10 > 0){
                    bill10--;
                    bill5--;
                }
                else{
                    bill5-=3;
                }
            }
            if(bill5 < 0 || bill10 < 0){
                return false;
            }
        }
        return true;
    }
}

可以發現貪心程式碼的程式碼大多相對單純，因為它就是挑選當下的局部最佳解，邏輯也單純。
從這題我們可以看出貪心算法的使用大概是：

確認問題的全局最佳解(找零要足夠)
拆分問題成若干個問題(每次不同錢的找零)
找出針對這些問題的局部最佳解(根據可取代性，優先找 10 塊，再找 5 塊，讓 5 塊盡量充足)
確認局部最佳解的邏輯達成後確實是全局最佳解(只要 5 塊是最充足的狀況下，還不能找零，表示這個例子無法找零)

這樣說起來可能有些模糊，但貪心的思路就在直觀，很多時後就直接試試看，通過定義的局部最佳得出的答案是不是全局最佳(透過邏輯與例子確認)，是的話就是貪心派上用場的時候。
貪心比較沒有那麼明顯可以用上的場合，總之就是試試看，如果行得通，那就行得通(很像廢話，但就是這樣)。

倒是有比較明顯是貪心無法作用的場合，在選項可能後續有更優解的時候，因為貪心算法一旦選擇就不會回退，所以如果在向後遍歷的過程中，可能會影響前面已結束的子問題，讓前面遍歷過的子問題有更優解的狀況下，貪心算法就不起效。
讓我們再來看幾題貪心的題目，感受一下貪心問題的作用場合。

Jump Game

跳躍遊戲的基礎版，每格代表可跳躍 0 ~ n 格距離，回傳是否有至少一條路能夠到達最後一個 index。
全局最優就是能到達最後一個 index。
局部最佳選擇是，應該挑選能跳到的地方中，跳到該處能幫我們跳最遠的。
這樣就能持續跳到最遠的地方往終點前進。
邏輯這樣就說完了。

程式碼的寫法是，把 options 是接下來能走的步數，如果接下來能走的步數加目前的 Index，已經能到最後一個 index，則回傳 true。
如果仍沒到最後一個 index，但能走的步數已經是 0(無路可走)，那就回傳 false。
接著是持續選擇能跳到的地方中最遠的地方，持續這個邏輯。

public class Solution {
    public bool CanJump(int[] nums) {
        var currentIndex = 0;
        while(true){
            var options = nums[currentIndex];
            if(currentIndex + options >= nums.Length - 1){
                return true;
            }
            if(options == 0){
                return false;
            }
            
            var max = -1;
            var maxI = -1;
            for(var i = 1; i <= options && (currentIndex + i) < nums.Length; i++){
                if(nums[currentIndex + i] + i>= max){
                    max = nums[currentIndex + i] + i;
                    maxI = i;
                }
            }     
                   
            currentIndex += maxI;
        }
        throw new Exception(); 
    }
}

主要要小心的就是邊界值，確認所有邊界值都有照顧到，比如一開始就 0 步，只有 1 個 element 的情況等等，貪心雖然寫起來簡單，但要顧慮的邊界細節往往也不少，這部分倒沒太多訣竅，就是多注意測資、確認測資邊界值是否有特別要處理的。

Jump Game II

跳躍問題第二題，陣列裡的意義都一樣，差在題目要求求出最小步數，同時題目保證至少有一組解能到終點。
邏輯幾乎一樣，我們甚至可以直接複製上題的程式碼，只有一個地方要注意，再看下去之前，希望你先想想。
.
.
.
好的，再來是程式碼

public class Solution {
    public int Jump(int[] nums) {
        if(nums.Length == 1){
            return 0;
        }
        var currentIndex = 0;
        var jumpTimes = 0;
        while(true){
            var options = nums[currentIndex];
            jumpTimes++;
            if(currentIndex + options >= nums.Length - 1){
                return jumpTimes;
            }
            
            var max = -1;
            var maxI = -1;
            for(var i = 1; i <= options && (currentIndex + i) < nums.Length; i++){
                if(nums[currentIndex + i] + i>= max){
                    max = nums[currentIndex + i] + i;
                    maxI = i;
                }
            }     
                   
            currentIndex += maxI;
        }
        throw new Exception(); 
    }
}

除去我們多計算了跳躍次數以外，這個情況多了一個特異值：如果一開始就在終點，也就是陣列長度為 1 的情況，是完全不用跳躍的，這就是貪心問題中需要注意的眉角。

貪心問題個人覺得多練習題目來找手感會比較合適，這邊留下 Leetcode 上貪心問題相關題單，一開始可以先就簡單難度的挑幾題做做，覺得差不多了再自己增加難度。
貪心問題的難點就是確認局部最佳解的組合會是全局最佳解，以及定義局部最佳解，邊界問題倒是老生常談，每種類型都要注意，這裡多提一嘴是因為貪心有時候寫得快了，會漏掉這個地方的謹慎。
明天我們就會進入動態規劃的章節，貪心的部分就以這篇帶過。