Java貪婪演演算法超詳細講解

什麼是貪婪演演算法

在分析和求解某個問題時，在每一步的計算選擇上都是最優的或者最好的，通過這種方式期望最終的計算的結果也是最優的。也就是說，演演算法通過先追求區域性的最優解，從而尋求整體的最優解。

貪婪演演算法的基本步驟：

1、首先定義問題，確定問題模型是不是適合使用貪婪演演算法，即求解最值問題；

2、將求極值的問題進行拆解，然後對拆解後的每一個子問題進行求解，試圖獲得當前子問題的區域性最優解；

3、所有子問題的區域性最優解求解完成後，把這些區域性最優解進行彙總合併，得到最終全域性的最優解，那麼這個最優解就是整個問題的最優解。

通過場景理解演演算法

概念性的演演算法描述可能大家都不太好理解，所以需要結合一些實際的場景來進行說明。這裡以我們小時候的找零錢的例子來進行切入。雖然現在大家都用手機掃一掃進行支付，已經很久到沒碰過錢了，但是並不妨礙找零問題 可幫助我們形象的理解貪婪演演算法的實現過程。

假設你是一家小賣店的老闆，你有各種面值大小的零錢，如1塊錢、3塊錢、5塊錢。這個時候有個小朋友過來買東西，他要求你找的零錢要張數最小，這樣他的口袋才能裝得下。假設我們分別把零錢記為c[0]、c[1]、c[2] ......，小朋友拿來買零食的錢我們記為total。那麼剛才說的小朋友希望獲得最少張數零錢的需求我們就可以把他轉化為一個程式設計求最優解的問題，即給定總數total，求解最少需要幾個c相加的和等於給定的總數total。

例子1：

假設給定需要找的零錢為11，當前的零錢為1塊、3塊、5塊。

輸入：total=11，c[0]=1,c[1]=3,c[2]=5

輸出：3

問題分析

通過提取問題中的關鍵詞“最少”，我們可以明確此問題的實際上就是一個求解最值的問題，只要找到滿足條件的最小零錢張數就可以解決找回最少零錢的問題了。想要找到最小的零錢張數，我們最先想到的方法就是進行窮舉，列舉出來所有可能的滿足總數為11的零錢組合。如下圖所示，再在這些組合中找到使用零錢張數最少的組合再計算具體的張數，我們就可以獲得最終的答案了。但是這顯然不是一個好的解決思路。因為如果對應的total很大，我們窮舉的結果將會爆發性增長。

那有沒有更好的解決辦法呢？這時候我們就可以考慮下貪婪演演算法的實現了，找到滿足要求的最小張數零錢。既然是找零錢，那麼我們可以將問題轉換為找到滿足總數total的零錢最少需要幾個步驟，實際上就是將問題拆分到每次找零錢的小步驟中，而貪婪演演算法的核心就是需要在每個小步驟中貪心尋求區域性最優解。因此在找零錢的每個步驟中，都需要找到該步驟中對應的最優解零錢大小，接下來我們來一起看下貪婪演演算法執行過程。這裡假設各個面值的零錢比較充足。

在尋找零錢的步驟中，首先獲取最大面值為5的零錢（貪心，上來就找最大的），接著發現剩餘待找零錢6=11-5，於是繼續尋找最大的面值為5的零錢（繼續貪心），待找零錢1=6-5。此時只要獲取面值為1的零錢就可以完成任務了，再將之前步驟中的結果整合到一起，最終我們得出想要獲取total為11的最少張數零錢的大小為3。通過這樣的分析，貪婪演演算法是不是也沒有那麼的複雜。

對應的程式碼實現如下所示：

 /**
 * @Author: mufeng
 * @Date: 2022/5/15 15:33
 * @Version: V 1.0.0
 * @Description: 計算最小滿足條件的零錢張數
 */
public class MinChangeCountSolution {
    public static void main(String[] args) {
        int values[] = {5,5,3,3,1};
        System.out.println(getMinChangeCount(11, values));
    }
    //假設values陣列從大到小排列
    static int getMinChangeCount(int total, int[] values) {
        int rest = total;
        int result = 0;
        int count = values.length;
        // 從大到小遍歷所有面值
        for (int i = 0; i < count; ++ i) {
            //計算需要幾張這種面值的零錢
            int needCount = rest / values[i];
            //計算使用後的餘額
            rest -= needCount * values[i];
            //計數增加
            result += needCount;
 
            if (rest == 0) {
                return result;
            }
        }
        //沒有找到合適的面值
        return -1;
    }
}

以上我們分析了貪婪演演算法的大致實現過程，但是實際上還是有問題的。不知道大家有沒有發現，由於貪婪演演算法過於貪心，每一個步驟都想要找到區域性最優解。那麼假如在上面的例子中，我們沒有1塊錢的零錢，上述程式碼的返回結果是-1，即沒有符合條件的答案。但是實際並非如此，也就是說5,3,3也是滿足條件的，但是上述程式碼卻沒有找到。

所以上述程式碼還是有問題的，關鍵點就在於，當發現沒有1元零錢的時候，需要回頭去看能不能把第二步驟中的5元零錢換成3元零錢再進行後續的迭代，如果有這樣的步驟，那麼就可以找到5,3,3這樣的組合。

總結

本文主要通過對於貪婪演演算法的描述，並結合實際的找零錢的例子，帶大家一起分析了貪婪演演算法的具體實現過程。同時分析了貪婪演演算法存在的不足，即容易陷入區域性最優的陷阱無法自拔，導致最終無法給出滿足條件的結果，這也是大家以後在使用貪婪演演算法分析問題時特別需要注意的問題。

到此這篇關於Java貪婪演演算法超詳細講解的文章就介紹到這了,更多相關Java貪婪演演算法內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！