什么是貪心算法

在分析和求解某個(gè)問(wèn)題時(shí)，在每一步的計(jì)算選擇上都是最優(yōu)的或者最好的，通過(guò)這種方式期望最終的計(jì)算的結(jié)果也是最優(yōu)的。也就是說(shuō)，算法通過(guò)先追求局部的最優(yōu)解，從而尋求整體的最優(yōu)解。

貪心算法的基本步驟：

1、首先定義問(wèn)題，確定問(wèn)題模型是不是適合使用貪心算法，即求解最值問(wèn)題；

2、將求極值的問(wèn)題進(jìn)行拆解，然后對(duì)拆解后的每一個(gè)子問(wèn)題進(jìn)行求解，試圖獲得當(dāng)前子問(wèn)題的局部最優(yōu)解；

3、所有子問(wèn)題的局部最優(yōu)解求解完成后，把這些局部最優(yōu)解進(jìn)行匯總合并，得到最終全局的最優(yōu)解，那么這個(gè)最優(yōu)解就是整個(gè)問(wèn)題的最優(yōu)解。

通過(guò)場(chǎng)景理解算法

概念性的算法描述可能大家都不太好理解，所以需要結(jié)合一些實(shí)際的場(chǎng)景來(lái)進(jìn)行說(shuō)明。這里以我們小時(shí)候的找零錢(qián)的例子來(lái)進(jìn)行切入。雖然現(xiàn)在大家都用手機(jī)掃一掃進(jìn)行支付，已經(jīng)很久到?jīng)]碰過(guò)錢(qián)了，但是并不妨礙找零問(wèn)題 可幫助我們形象的理解貪心算法的實(shí)現(xiàn)過(guò)程。

假設(shè)你是一家小賣(mài)店的老板，你有各種面值大小的零錢(qián)，如1塊錢(qián)、3塊錢(qián)、5塊錢(qián)。這個(gè)時(shí)候有個(gè)小朋友過(guò)來(lái)買(mǎi)東西，他要求你找的零錢(qián)要張數(shù)最小，這樣他的口袋才能裝得下。假設(shè)我們分別把零錢(qián)記為c[0]、c[1]、c[2] ......，小朋友拿來(lái)買(mǎi)零食的錢(qián)我們記為total。那么剛才說(shuō)的小朋友希望獲得最少?gòu)垟?shù)零錢(qián)的需求我們就可以把他轉(zhuǎn)化為一個(gè)編程求最優(yōu)解的問(wèn)題，即給定總數(shù)total，求解最少需要幾個(gè)c相加的和等于給定的總數(shù)total。

例子1：

假設(shè)給定需要找的零錢(qián)為11，當(dāng)前的零錢(qián)為1塊、3塊、5塊。

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

輸出：3

問(wèn)題分析

通過(guò)提取問(wèn)題中的關(guān)鍵詞“最少”，我們可以明確此問(wèn)題的實(shí)際上就是一個(gè)求解最值的問(wèn)題，只要找到滿足條件的最小零錢(qián)張數(shù)就可以解決找回最少零錢(qián)的問(wèn)題了。想要找到最小的零錢(qián)張數(shù)，我們最先想到的方法就是進(jìn)行窮舉，列舉出來(lái)所有可能的滿足總數(shù)為11的零錢(qián)組合。如下圖所示，再在這些組合中找到使用零錢(qián)張數(shù)最少的組合再計(jì)算具體的張數(shù)，我們就可以獲得最終的答案了。但是這顯然不是一個(gè)好的解決思路。因?yàn)槿绻麑?duì)應(yīng)的total很大，我們窮舉的結(jié)果將會(huì)爆發(fā)性增長(zhǎng)。

那有沒(méi)有更好的解決辦法呢？這時(shí)候我們就可以考慮下貪心算法的實(shí)現(xiàn)了，找到滿足要求的最小張數(shù)零錢(qián)。既然是找零錢(qián)，那么我們可以將問(wèn)題轉(zhuǎn)換為找到滿足總數(shù)total的零錢(qián)最少需要幾個(gè)步驟，實(shí)際上就是將問(wèn)題拆分到每次找零錢(qián)的小步驟中，而貪心算法的核心就是需要在每個(gè)小步驟中貪心尋求局部最優(yōu)解。因此在找零錢(qián)的每個(gè)步驟中，都需要找到該步驟中對(duì)應(yīng)的最優(yōu)解零錢(qián)大小，接下來(lái)我們來(lái)一起看下貪心算法執(zhí)行過(guò)程。這里假設(shè)各個(gè)面值的零錢(qián)比較充足。

在尋找零錢(qián)的步驟中，首先獲取最大面值為5的零錢(qián)（貪心，上來(lái)就找最大的），接著發(fā)現(xiàn)剩余待找零錢(qián)6=11-5，于是繼續(xù)尋找最大的面值為5的零錢(qián)（繼續(xù)貪心），待找零錢(qián)1=6-5。此時(shí)只要獲取面值為1的零錢(qián)就可以完成任務(wù)了，再將之前步驟中的結(jié)果整合到一起，最終我們得出想要獲取total為11的最少?gòu)垟?shù)零錢(qián)的大小為3。通過(guò)這樣的分析，貪心算法是不是也沒(méi)有那么的復(fù)雜。

對(duì)應(yīng)的代碼實(shí)現(xiàn)如下所示：

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

以上我們分析了貪心算法的大致實(shí)現(xiàn)過(guò)程，但是實(shí)際上還是有問(wèn)題的。不知道大家有沒(méi)有發(fā)現(xiàn)，由于貪心算法過(guò)于貪心，每一個(gè)步驟都想要找到局部最優(yōu)解。那么假如在上面的例子中，我們沒(méi)有1塊錢(qián)的零錢(qián)，上述代碼的返回結(jié)果是-1，即沒(méi)有符合條件的答案。但是實(shí)際并非如此，也就是說(shuō)5,3,3也是滿足條件的，但是上述代碼卻沒(méi)有找到。

所以上述代碼還是有問(wèn)題的，關(guān)鍵點(diǎn)就在于，當(dāng)發(fā)現(xiàn)沒(méi)有1元零錢(qián)的時(shí)候，需要回頭去看能不能把第二步驟中的5元零錢(qián)換成3元零錢(qián)再進(jìn)行后續(xù)的迭代，如果有這樣的步驟，那么就可以找到5,3,3這樣的組合。

總結(jié)

本文主要通過(guò)對(duì)于貪心算法的描述，并結(jié)合實(shí)際的找零錢(qián)的例子，帶大家一起分析了貪心算法的具體實(shí)現(xiàn)過(guò)程。同時(shí)分析了貪心算法存在的不足，即容易陷入局部最優(yōu)的陷阱無(wú)法自拔，導(dǎo)致最終無(wú)法給出滿足條件的結(jié)果，這也是大家以后在使用貪心算法分析問(wèn)題時(shí)特別需要注意的問(wèn)題。

到此這篇關(guān)于Java貪心算法超詳細(xì)講解的文章就介紹到這了,更多相關(guān)Java貪心算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論