???? 前面小編主要分享了使用到分治策略的經(jīng)典排序算法渺尘，接下來小編要來分享下另外一個(gè)經(jīng)典的算法，也就是貪心算法说敏。貪心算法有很多經(jīng)典的應(yīng)用鸥跟，比如霍夫曼編碼（Huffman Coding）、Prim 和 Kruskal 最小生成樹算法、還有 Dijkstra 單源最短路徑算法医咨。這些算法后續(xù)小編都會(huì)進(jìn)行分享枫匾，今天小編先簡單介紹下什么是“貪心算法”。
一拟淮、貪心本質(zhì)
??? 我們經(jīng)常會(huì)聽到這些話：“人要活在當(dāng)下”干茉，“看清楚眼前”……。貪心算法正是“活在當(dāng)下很泊，看清楚眼前”的辦法角虫，從問題的初始解開始，一步一歩地做出當(dāng)前最好的選擇委造，逐步逼近問題的目標(biāo)上遥，盡可能地得到最優(yōu)解，即使達(dá)不到最優(yōu)解争涌，也可以得到最優(yōu)解的近似解粉楚。
??? 貪心算法在解決問題的策略上“目光短淺”，只根據(jù)當(dāng)前已有的信息就做出選擇亮垫，而且一旦做出了選擇模软，不管將來有什么結(jié)果，這個(gè)選擇都不會(huì)改變饮潦。換言之燃异，貪心算法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)继蜡。貪心算法能得到許多問題的整體最優(yōu)解或整體最優(yōu)解的近似解回俐。因此，貪心算法在實(shí)際中得到大量的應(yīng)用稀并。
??? 在貪心算法中仅颇，我們需要注意以下幾個(gè)問題
??? （1）沒有后悔藥。一旦做出選擇碘举，不可以反悔
??? （2）有可能得到的不是最優(yōu)解忘瓦，而是最優(yōu)解的近似解
??? （3）選擇什么樣的貪心策略，直接決定算法的好壞
二引颈、貪心算法遵循的原則
??? 那么耕皮，貪心算法需要遵循什么樣的原則呢？
??? “君子愛財(cái)蝙场，取之有道”凌停，我們?cè)谪澬乃惴ㄖ小柏澮嘤械馈薄ＭǔＮ覀冊(cè)谟龅骄唧w問題時(shí)售滤，往往分不清哪些問題該用貪心策略求解罚拟，哪些問題不能使用貪心策略。經(jīng)過實(shí)踐我們發(fā)現(xiàn)，利用貪心算法求解的問題往往具有兩個(gè)重要的特性：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)舟舒。如果滿足這兩個(gè)性質(zhì)就可以使用貪心算法了。
??? （1）貪心選擇
??? 所謂貪心選擇性質(zhì)是指原問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇得到嗜憔。應(yīng)用同一規(guī)則秃励，將原問題變?yōu)橐粋€(gè)相似的但規(guī)模更小的子問題，而后的每一步都是當(dāng)前最佳的選擇吉捶。這種選擇依賴于已做出的選擇夺鲜，但不依賴于未做出的選擇。運(yùn)用貪心策略解決的問題在程序的運(yùn)行過程中無回溯過程呐舔。
??? （2）最優(yōu)子結(jié)構(gòu)
??? 當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)币励，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題是否可用貪心算法求解的關(guān)鍵珊拼。例如原問題S={a1食呻，a2，…澎现，ai仅胞，…，an}剑辫，通過貪心選擇選出一個(gè)當(dāng)前最優(yōu)解{ai}之后干旧，轉(zhuǎn)化為求解子問題S?{ai}，如果原問題的最優(yōu)解包含子問題的最優(yōu)解妹蔽，則說明該問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)椎眯。其實(shí)就是所謂的集合中的包含關(guān)系。
三胳岂、貪心算法秘籍
??? 武林中有武功秘籍编整，算法中也有貪心秘籍。上面我們已經(jīng)知道了具有貪心選擇和最優(yōu)子結(jié)構(gòu)性質(zhì)就可以使用貪心算法乳丰，那么如何使用呢闹击？下面介紹貪心算法秘籍。
??? （1）貪心策略
??? 首先要確定貪心策略成艘，選擇當(dāng)前看上去最好的一個(gè)方案赏半。例如，挑選蘋果淆两，如果你認(rèn)為個(gè)大的是最好的断箫，那你每次都從蘋果堆中拿一個(gè)最大的，作為局部最優(yōu)解秋冰，貪心策略就是選擇當(dāng)前最大的蘋果仲义；如果你認(rèn)為最紅的蘋果是最好的，那你每次都從蘋果堆中拿一個(gè)最紅的，貪心策略就是選擇當(dāng)前最紅的蘋果埃撵。因此根據(jù)求解目標(biāo)不同赵颅，貪心策略也會(huì)不同。
??? （2）局部最優(yōu)解
??? 根據(jù)貪心策略暂刘，一步一步地得到局部最優(yōu)解饺谬。例如，第一次選一個(gè)最大的蘋果放起來谣拣，記為a1募寨，第二次再從剩下的蘋果堆中選擇一個(gè)最大的蘋果放起來，記為a2森缠，以此類推拔鹰。
??? （3）全局最優(yōu)解
??? 把所有的局部最優(yōu)解合成為原來問題的一個(gè)最優(yōu)解（a1，a2贵涵，…）列肢。
??? 怎么有點(diǎn)兒像冒泡排序啊宾茂？
??? 其實(shí)不是貪心算法像冒泡排序例书，而是冒泡排序使用了貪心算法，它的貪心策略就是每一次從剩下的序列中選一個(gè)最大的數(shù)刻炒，把這些選出來的數(shù)放在一起决采，就得到了從大到小的排序結(jié)果。
四坟奥、例子簡析之貨幣選擇問題
??? 問題描述：分別有1,5,10,50,100元树瞭，分別有5,2,2,3,5張紙幣。問若要支付k元爱谁，則需要多少張紙幣晒喷？
??? 問題分析：
??? 我們只需要遵循“優(yōu)先使用面值大的硬幣”即可。
??? 1访敌、盡可能多的使用100元（即最大的）
??? 2凉敲、余下部分盡可能多的使用50元
??? 3、余下部分盡可能多的使用10元
??? 4寺旺、余下部分盡可能多的使用5元
??? 5爷抓、余下部分使用1元
??? 代碼截圖：
參考：貪心算法秘籍 - 簡書
