一口锭、貪心算法：
1曲楚、概念：
??每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)（即最有利）的選擇厘唾，從而希望導(dǎo)致結(jié)果是最好或最優(yōu)的算法。
2龙誊、貪心算法解決問題的思路抚垃，并不一定能給出最優(yōu)解：
??在一個有權(quán)圖中，從頂點S開始趟大，找一條到頂點T的最短路徑（路徑中邊的權(quán)值和最泻资鳌）。貪心算法的解決思路是逊朽，每次都選擇一條跟當(dāng)前頂點相連的權(quán)最小的邊罕伯，直到找到頂點T。按照這種思路叽讳，求出的最短路徑是S->A->E->T追他，路徑長度是1+4+4=9。這種貪心的選擇方式岛蚤，最終求的路徑并不是最短路徑邑狸，因為路徑S->B->D->T才是最短路徑，因為這條路徑的長度是2+2+2=6涤妒。
??在這個問題上单雾，貪心算法不工作的主要原因是，前面的選擇會影響后面的選擇届腐。如果第一步從頂點S走到頂點A铁坎，那接下來面對的頂點和邊，跟第一步從頂點S走到頂點B犁苏，是完全不同的硬萍。所以，即便第一步選擇最優(yōu)的走法（邊最短）围详，但有可能因為這一步選擇朴乖，導(dǎo)致后面每一步的選擇都很糟糕，最終也就無緣全局最優(yōu)解了助赞。
二买羞、實戰(zhàn)分析：
1、分糖果：
??有個糖果和
個孩子”⑹常現(xiàn)在要把糖果分給這些孩子吃畜普，但是糖果少，孩子多（
）群叶，所以糖果只能分配給一部分孩子吃挑。每個糖果的大小不等钝荡，這
個糖果的大小分別是
，
舶衬，
,……,
埠通。除此之外，每個孩子對糖果大小的需求也是不一樣的逛犹，只有糖果的大小大于等于孩子的對糖果大小的需求的時候端辱，孩子才得到滿足。假設(shè)這
個孩子對糖果大小的需求分別是
虽画，
舞蔽，
， ……狸捕，
喷鸽。問題是，如何分配糖果灸拍，能盡可能滿足最多數(shù)量的孩子做祝？
??把這個問題抽象成，從個孩子中鸡岗，抽取一部分孩子分配糖果混槐，讓滿足的孩子的個數(shù)（期望值）是最大的。這個問題的限制值就是糖果個數(shù)
轩性。
??對于一個孩子來說声登，如果小的糖果可以滿足，就沒必要用更大的糖果揣苏，這樣更大的就可以留給其他對糖果大小需求更大的孩子悯嗓。另一方面，對糖果大小需求小的孩子更容易被滿足卸察，所以脯厨，可以從需求小的孩子開始分配糖果。因為滿足一個需求大的孩子跟滿足一個需求小的孩子坑质，對期望值的貢獻是一樣的合武。每次從剩下的孩子中，找出對糖果大小需求最小的涡扼，然后發(fā)給他剩下的糖果中能滿足他的最小的糖果稼跳，這樣得到的分配方案，也就是滿足的孩子個數(shù)最多的方案吃沪。
2汤善、錢幣找零：
??假設(shè)有、
、
红淡、
卸伞、
、
锉屈、
這些面額的紙幣，它們的張數(shù)分別是
垮耳、
颈渊、
、
终佛、
俊嗽、
、
×逭茫現(xiàn)在要用這些錢來支付
元绍豁，最少要用多少張紙幣呢？
??先用面值最大的來支付牙捉，如果不夠竹揍，就繼續(xù)用更小一點面值的，以此類推邪铲，最后剩下的用來補齊芬位。
3、區(qū)間覆蓋：
??假設(shè)有個區(qū)間带到，區(qū)間的起始端點和結(jié)束端點分別是
昧碉，
，
揽惹， …
被饿。從這
個區(qū)間中選出一部分區(qū)間，這部分區(qū)間滿足兩兩不相交（端點相交的情況不算相交）搪搏，最多能選出多少個區(qū)間呢狭握？
??假設(shè)這個區(qū)間中最左端點是
，最右端點是
慕嚷。這個問題就相當(dāng)于選擇幾個不相交的區(qū)間哥牍，從左到右將
覆蓋上。按照起始端點從小到大的順序?qū)@
個區(qū)間排序喝检，每次選擇的時候嗅辣，左端點跟前面的已經(jīng)覆蓋的區(qū)間不重合的，右端點又盡量小的挠说，這樣可以讓剩下的未覆蓋區(qū)間盡可能的大澡谭，就可以放置更多的區(qū)間。這實際上就是一種貪心的選擇方法。
4蛙奖、Huffman編碼：
??假設(shè)有一個包含1000個字符的文件潘酗，節(jié)省空間的存儲方式怎么存儲？
??假設(shè)這6個字符出現(xiàn)的頻率從高到低依次是a雁仲、 b仔夺、 c、 d攒砖、 e缸兔、 f。把它們編碼下面這個樣子吹艇，任何一個字符的編碼都不是另一個的前綴惰蜜，在解壓縮的時候，每次會讀取盡可能長的可解壓的二進制串受神，所以在解壓縮的時候也不會歧義抛猖。
??把每個字符看作一個節(jié)點，并且輔帶著把頻率放到優(yōu)先級隊列中鼻听。從隊列中取出頻率最小的兩個節(jié)點A财著、 B，然后新建一個節(jié)點C精算，把頻率設(shè)置為兩個節(jié)點的頻率之和瓢宦，并把這個新節(jié)點C作為節(jié)點A、 B的父節(jié)點灰羽。最后再把C節(jié)點放入到優(yōu)先級隊列中驮履。重復(fù)這個過程，直到隊列中沒有數(shù)據(jù)廉嚼。
給每一條邊加上畫一個權(quán)值玫镐，指向左子節(jié)點的邊我們統(tǒng)統(tǒng)標(biāo)記為0，指向右子節(jié)點的邊怠噪，我們統(tǒng)統(tǒng)標(biāo)記為1恐似，那從根節(jié)點到葉節(jié)點的路徑就是葉節(jié)點對應(yīng)字符的霍夫曼編碼為：
