一、貪心算法：
1、概念：
??每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)（即最有利）的選擇，從而希望導(dǎo)致結(jié)果是最好或最優(yōu)的算法。
2、貪心算法解決問(wèn)題的思路，并不一定能給出最優(yōu)解：
??在一個(gè)有權(quán)圖中，從頂點(diǎn)S開始，找一條到頂點(diǎn)T的最短路徑（路徑中邊的權(quán)值和最小）。貪心算法的解決思路是，每次都選擇一條跟當(dāng)前頂點(diǎn)相連的權(quán)最小的邊，直到找到頂點(diǎn)T。按照這種思路，求出的最短路徑是S->A->E->T，路徑長(zhǎng)度是1+4+4=9。這種貪心的選擇方式，最終求的路徑并不是最短路徑，因?yàn)槁窂絊->B->D->T才是最短路徑，因?yàn)檫@條路徑的長(zhǎng)度是2+2+2=6。
??在這個(gè)問(wèn)題上，貪心算法不工作的主要原因是，前面的選擇會(huì)影響后面的選擇。如果第一步從頂點(diǎn)S走到頂點(diǎn)A，那接下來(lái)面對(duì)的頂點(diǎn)和邊，跟第一步從頂點(diǎn)S走到頂點(diǎn)B，是完全不同的。所以，即便第一步選擇最優(yōu)的走法（邊最短），但有可能因?yàn)檫@一步選擇，導(dǎo)致后面每一步的選擇都很糟糕，最終也就無(wú)緣全局最優(yōu)解了。
二、實(shí)戰(zhàn)分析：
1、分糖果：
??有個(gè)糖果和
個(gè)孩子?，F(xiàn)在要把糖果分給這些孩子吃，但是糖果少，孩子多（
），所以糖果只能分配給一部分孩子。每個(gè)糖果的大小不等，這
個(gè)糖果的大小分別是
，
，
,……,
。除此之外，每個(gè)孩子對(duì)糖果大小的需求也是不一樣的，只有糖果的大小大于等于孩子的對(duì)糖果大小的需求的時(shí)候，孩子才得到滿足。假設(shè)這
個(gè)孩子對(duì)糖果大小的需求分別是
，
，
， ……，
。問(wèn)題是，如何分配糖果，能盡可能滿足最多數(shù)量的孩子？
??把這個(gè)問(wèn)題抽象成，從個(gè)孩子中，抽取一部分孩子分配糖果，讓滿足的孩子的個(gè)數(shù)（期望值）是最大的。這個(gè)問(wèn)題的限制值就是糖果個(gè)數(shù)
。
??對(duì)于一個(gè)孩子來(lái)說(shuō)，如果小的糖果可以滿足，就沒(méi)必要用更大的糖果，這樣更大的就可以留給其他對(duì)糖果大小需求更大的孩子。另一方面，對(duì)糖果大小需求小的孩子更容易被滿足，所以，可以從需求小的孩子開始分配糖果。因?yàn)闈M足一個(gè)需求大的孩子跟滿足一個(gè)需求小的孩子，對(duì)期望值的貢獻(xiàn)是一樣的。每次從剩下的孩子中，找出對(duì)糖果大小需求最小的，然后發(fā)給他剩下的糖果中能滿足他的最小的糖果，這樣得到的分配方案，也就是滿足的孩子個(gè)數(shù)最多的方案。
2、錢幣找零：
??假設(shè)有、
、
、
、
、
、
這些面額的紙幣，它們的張數(shù)分別是
、
、
、
、
、
、
?，F(xiàn)在要用這些錢來(lái)支付
元，最少要用多少?gòu)埣垘拍兀?/p>
??先用面值最大的來(lái)支付，如果不夠，就繼續(xù)用更小一點(diǎn)面值的，以此類推，最后剩下的用來(lái)補(bǔ)齊。
3、區(qū)間覆蓋：
??假設(shè)有個(gè)區(qū)間，區(qū)間的起始端點(diǎn)和結(jié)束端點(diǎn)分別是
，
，
， …
。從這
個(gè)區(qū)間中選出一部分區(qū)間，這部分區(qū)間滿足兩兩不相交（端點(diǎn)相交的情況不算相交），最多能選出多少個(gè)區(qū)間呢？
??假設(shè)這個(gè)區(qū)間中最左端點(diǎn)是
，最右端點(diǎn)是
。這個(gè)問(wèn)題就相當(dāng)于選擇幾個(gè)不相交的區(qū)間，從左到右將
覆蓋上。按照起始端點(diǎn)從小到大的順序?qū)@
個(gè)區(qū)間排序，每次選擇的時(shí)候，左端點(diǎn)跟前面的已經(jīng)覆蓋的區(qū)間不重合的，右端點(diǎn)又盡量小的，這樣可以讓剩下的未覆蓋區(qū)間盡可能的大，就可以放置更多的區(qū)間。這實(shí)際上就是一種貪心的選擇方法。
4、Huffman編碼：
??假設(shè)有一個(gè)包含1000個(gè)字符的文件，節(jié)省空間的存儲(chǔ)方式怎么存儲(chǔ)？
??假設(shè)這6個(gè)字符出現(xiàn)的頻率從高到低依次是a、 b、 c、 d、 e、 f。把它們編碼下面這個(gè)樣子，任何一個(gè)字符的編碼都不是另一個(gè)的前綴，在解壓縮的時(shí)候，每次會(huì)讀取盡可能長(zhǎng)的可解壓的二進(jìn)制串，所以在解壓縮的時(shí)候也不會(huì)歧義。
??把每個(gè)字符看作一個(gè)節(jié)點(diǎn)，并且輔帶著把頻率放到優(yōu)先級(jí)隊(duì)列中。從隊(duì)列中取出頻率最小的兩個(gè)節(jié)點(diǎn)A、 B，然后新建一個(gè)節(jié)點(diǎn)C，把頻率設(shè)置為兩個(gè)節(jié)點(diǎn)的頻率之和，并把這個(gè)新節(jié)點(diǎn)C作為節(jié)點(diǎn)A、 B的父節(jié)點(diǎn)。最后再把C節(jié)點(diǎn)放入到優(yōu)先級(jí)隊(duì)列中。重復(fù)這個(gè)過(guò)程，直到隊(duì)列中沒(méi)有數(shù)據(jù)。
給每一條邊加上畫一個(gè)權(quán)值，指向左子節(jié)點(diǎn)的邊我們統(tǒng)統(tǒng)標(biāo)記為0，指向右子節(jié)點(diǎn)的邊，我們統(tǒng)統(tǒng)標(biāo)記為1，那從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑就是葉節(jié)點(diǎn)對(duì)應(yīng)字符的霍夫曼編碼為：
