『算法』『數(shù)據(jù)結(jié)構(gòu)』 淺談貪心算法俭尖,理解程序員必懂必會的計算機常見算法——貪心算法

基本認(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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末拆讯,一起剝皮案震驚了整個濱河市养叛,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌爽室,老刑警劉巖淆攻,帶你破解...
    沈念sama閱讀 221,430評論 6 515
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件瓶珊,死亡現(xiàn)場離奇詭異,居然都是意外死亡伞芹,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,406評論 3 398
  • 文/潘曉璐 我一進(jìn)店門蜀肘,熙熙樓的掌柜王于貴愁眉苦臉地迎上來稽屏,“玉大人,你說我怎么就攤上這事坛增”∧澹” “怎么了?”我有些...
    開封第一講書人閱讀 167,834評論 0 360
  • 文/不壞的土叔 我叫張陵罢艾,是天一觀的道長尽纽。 經(jīng)常有香客問我弄贿,道長,這世上最難降的妖魔是什么差凹? 我笑而不...
    開封第一講書人閱讀 59,543評論 1 296
  • 正文 為了忘掉前任危尿,我火速辦了婚禮,結(jié)果婚禮上肺孤,老公的妹妹穿的比我還像新娘邮绿。我一直安慰自己攀例,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 68,547評論 6 397
  • 文/花漫 我一把揭開白布挖胃。 她就那樣靜靜地躺著,像睡著了一般吗垮。 火紅的嫁衣襯著肌膚如雪凹髓。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,196評論 1 308
  • 那天饵沧,我揣著相機與錄音,去河邊找鬼赌躺。 笑死狼牺,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的礼患。 我是一名探鬼主播是钥,決...
    沈念sama閱讀 40,776評論 3 421
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼缅叠!你這毒婦竟也來了悄泥?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,671評論 0 276
  • 序言:老撾萬榮一對情侶失蹤痪署,失蹤者是張志新(化名)和其女友劉穎码泞,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體余寥,經(jīng)...
    沈念sama閱讀 46,221評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,303評論 3 340
  • 正文 我和宋清朗相戀三年悯森,在試婚紗的時候發(fā)現(xiàn)自己被綠了宋舷。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,444評論 1 352
  • 序言:一個原本活蹦亂跳的男人離奇死亡瓢姻,死狀恐怖祝蝠,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情幻碱,我是刑警寧澤绎狭,帶...
    沈念sama閱讀 36,134評論 5 350
  • 正文 年R本政府宣布,位于F島的核電站褥傍,受9級特大地震影響儡嘶,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜恍风,卻給世界環(huán)境...
    茶點故事閱讀 41,810評論 3 333
  • 文/蒙蒙 一蹦狂、第九天 我趴在偏房一處隱蔽的房頂上張望誓篱。 院中可真熱鬧,春花似錦凯楔、人聲如沸窜骄。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,285評論 0 24
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽邻遏。三九已至,卻和暖如春虐骑,著一層夾襖步出監(jiān)牢的瞬間党远,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,399評論 1 272
  • 我被黑心中介騙來泰國打工富弦, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留沟娱,地道東北人。 一個月前我還...
    沈念sama閱讀 48,837評論 3 376
  • 正文 我出身青樓腕柜,卻偏偏與公主長得像济似,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子盏缤,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,455評論 2 359

推薦閱讀更多精彩內(nèi)容