基本認(rèn)識

貪心算法（又稱貪婪算法）是指洞翩，在對問題求解時骚亿，總是做出在當(dāng)前看來是最好的選擇熊赖。也就是說，不從整體最優(yōu)上加以考慮震鹉，它所做出的是在某種意義上的局部最優(yōu)解传趾。

基本思想與原理

貪心選擇是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到浆兰。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別榕订。貪心選擇是采用從頂向下蝶棋、以迭代的方法做出相繼選擇，每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題兼贸。對于一個具體問題吃溅，要確定它是否具有貪心選擇的性質(zhì)，我們必須證明每一步所作的貪心選擇最終能得到問題的最優(yōu)解螺垢。通忱蹈瑁可以首先證明問題的一個整體最優(yōu)解，是從貪心選擇開始的庐冯，而且作了貪心選擇后展父，原問題簡化為一個規(guī)模更小的類似子問題玲昧。然后篮绿，用數(shù)學(xué)歸納法證明，通過每一步貪心選擇亲配，最終可得到問題的一個整體最優(yōu)解吼虎。

貪心算法的基本思路是從問題的某一個初始解出發(fā)一步一步地進(jìn)行，每一步都要確保能獲得局部最優(yōu)解鲸睛。每一步只考慮一個數(shù)據(jù)官辈，他的選取應(yīng)該滿足局部優(yōu)化的條件遍坟。若下一個數(shù)據(jù)和部分最優(yōu)解連在一起不再是可行解時，就不把該數(shù)據(jù)添加到部分解中愿伴，直到把所有數(shù)據(jù)枚舉完隔节，或者不能再添加算法停止。

適用的問題

貪心策略適用的前提是：局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解怎诫。
實際上幻妓，貪心算法適用的情況很少。一般對一個問題分析是否適用于貪心算法肉津，可以先選擇該問題下的幾個實際數(shù)據(jù)進(jìn)行分析，就可以做出判斷偶洋。

大多數(shù)可以使用貪心算法的問題都有以下特點：
（1）原問題復(fù)雜度過高初烘；
（2）求全局最優(yōu)解的數(shù)學(xué)模型難以建立分俯；
（3）求全局最優(yōu)解的計算量過大哆料；
（4）沒有太大必要一定要求出全局最優(yōu)解东亦，“比較優(yōu)”就可以。

嚴(yán)格來說典阵，貪婪算法可解決的問題通常大部分都有如下的特性：
（1）隨著算法的進(jìn)行壮啊，將積累起其它兩個集合：一個包含已經(jīng)被考慮過并被選出的候選對象，另一個包含已經(jīng)被考慮過但被丟棄的候選對象歹啼。
（2）有一個函數(shù)來檢查一個候選對象的集合是否提供了問題的解答狸眼。該函數(shù)不考慮此時的解決方法是否最優(yōu)。
（3）還有一個函數(shù)檢查是否一個候選對象的集合是可行的拓萌，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數(shù)一樣屡限，此時不考慮解決方法的最優(yōu)性炕倘。
（4）選擇函數(shù)可以指出哪一個剩余的候選對象最有希望構(gòu)成問題的解。
（5）最后拓型，目標(biāo)函數(shù)給出解的值瘸恼。
（6）為了解決問題，需要尋找一個構(gòu)成解的候選對象集合压固，它可以優(yōu)化目標(biāo)函數(shù)靠闭，貪婪算法一步一步的進(jìn)行坎炼。起初拦键，算法選出的候選對象的集合為空芬为。接下來的每一步中，根據(jù)選擇函數(shù)媚朦，算法從剩余候選對象中選出最有希望構(gòu)成解的對象。如果集合中加上該對象后不可行孙乖，那么該對象就被丟棄并不再考慮份氧；否則就加到集合里。每一次都擴充集合，并檢查該集合是否構(gòu)成解钮糖。如果貪婪算法正確工作酌住，那么找到的第一個解通常是最優(yōu)的。

求解的步驟與模板

貪婪算法并沒有固定的算法解決框架消痛，算法的關(guān)鍵是貪婪策略的選擇都哭，根據(jù)不同的問題選擇不同的策略。

必須注意的是策略的選擇必須具備無后效性纱新，即某個狀態(tài)的選擇不會影響到之前的狀態(tài)穆趴，只與當(dāng)前狀態(tài)有關(guān)，所以對采用的貪婪的策略一定要仔細(xì)分析其是否滿足無后效性簿废。

引例部分

活動安排問題：
設(shè)有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源歪赢，如演講會場等导梆，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si <fi 看尼。如果選擇了活動i藏斩，則它在半開時間區(qū)間[si, fi)內(nèi)占用資源。若區(qū)間[si, fi)與區(qū)間[sj, fj)不相交媳拴，則稱活動i與活動j是相容的兆览。也就是說，當(dāng)si≥fj或sj≥fi時子巾，活動i與活動j相容小压。活動安排問題： 要在所給的活動集合中選出最大的相容活動子集合怠益◎呃危活動安排問題的關(guān)鍵是如何按照一定的順序安排活動，使得選出的活動間相容并能安排盡量多的活動髓削。

在這里插入圖片描述

解題思路：
把會場要安排的所有活動作為一個集合W镀娶，初始開始時間標(biāo)準(zhǔn)為preStart,初始結(jié)束時間標(biāo)準(zhǔn)為preEnd.每次放入W的活動要在滿足，開始時間s[i]>preStart的前提下f[i]最小宝泵。然后把f[i]賦值給preStart. 依次加入，直到加不進(jìn)去為止框往，從而把問題解決。

雖然貪心算法并不是針對任何一個問題都存在最優(yōu)解瓤鼻，但是針對會場安排問題可以得到最優(yōu)解。我們可以從貪心算法得到的結(jié)果集僅進(jìn)行倒推茬祷。首先去掉結(jié)果集中的第一個活動A祭犯，那么在剩下的活動中，結(jié)束時間最早的活動B的結(jié)束時間一定不早于A,那么A活動在最優(yōu)解中一定合理粥惧。再用同樣的方式判斷活動B,依次類推最盅，則結(jié)果集就是最優(yōu)解。

實戰(zhàn)部分

整數(shù)轉(zhuǎn)羅馬數(shù)字問題：

在這里插入圖片描述

在這里插入圖片描述

解題思路：
這道題要將4，9盼产，40勺馆，90，400灌灾，900的符號單列出來悲柱。然后我們使用貪心算法，每次運算都將總數(shù)減去最大的可能數(shù)值嘿般，直到減到0。（就像假如你要付67塊錢逼庞，肯定先找出一張50塊瞻赶，再找出一張10塊，再找出一張5塊璧南，最后找出兩張1塊）痹兜。

下面附上Python3的題解代碼

class Solution:
    def intToRoman(self, num: int) -> str:
        dic={'I':1,'IV':4,'V':5,'IX':9,'X':10,'XL':40,'L':50,'XC':90,'C':100,'CD':400,'D':500,'CM':900,'M':1000}
        res=""
        for val in sorted(dic.values())[::-1]:
            if num==0:
                break
            tmp=num//val
            if tmp==0:
                continue
            res +=(list (dic.keys()) [list (dic.values()).index (val)])*tmp
            num -=val*tmp
        return res

趁熱打鐵 刷題練習(xí)部分（持續(xù)更新）

以下是LeetCode題庫中一些用到貪心算法的經(jīng)典例題的題目及解析字旭，有題干，有題解代碼拍柒、有解題思路（持續(xù)更新）：

No.12.整數(shù)轉(zhuǎn)羅馬字母：
https://blog.csdn.net/LanXiu_/article/details/104085783

No.13.羅馬數(shù)字轉(zhuǎn)整數(shù):
https://blog.csdn.net/LanXiu_/article/details/104085783

No.45.跳躍游戲Ⅱ:
https://blog.csdn.net/LanXiu_/article/details/104177349

No.55.跳躍游戲：
https://blog.csdn.net/LanXiu_/article/details/104216342