貪心算法解決問題的步驟
第一步，當我們看到這類問題的時候束倍，首先要聯(lián)想到貪心算法：針對一組數(shù)據(jù)，我們定義了限制值和期望值茶没，希望從中選出幾個數(shù)據(jù)肌幽，在滿足限制值的情況下，期滿值最大抓半。
第二步谎懦，我們嘗試看下這個問題是否可以用貪心算法解決：每次選擇當前情況下脯倒，在對限制值等同貢獻值的情況下，對期望值貢獻最大的數(shù)據(jù)剩晴。
第三步，我們舉個例子看下貪心算法產(chǎn)生的結(jié)果是否最優(yōu)的特占。
貪心算法實戰(zhàn)分析
分糖果
我們有m個糖果盒n個孩子。我們現(xiàn)在要把糖果分給這些孩子吃，但是糖果少懂诗，孩子多（m<n)，所以糖果只能分配給一部分孩子苗膝。如何分配糖果殃恒，能盡可能滿足最多數(shù)量的孩子？
解答：我們每次從剩下的孩子中辱揭，找出對糖果大小需求最小的离唐，然后發(fā)給他剩下的糖果中能滿足他的最小的糖果。錢幣找零
假設(shè)我們有1元问窃、2元亥鬓、5元、10元域庇、20元嵌戈、50元、100元這些面額的紙幣听皿，它們的張數(shù)分別是c1熟呛、c2、c5写穴、c10惰拱、c20、c50啊送、c100偿短。我們現(xiàn)在要用這些錢來支付K元，最少要用多少張紙幣馋没？
解答：在貢獻相同期望值（紙幣數(shù)目）的情況下昔逗，我們希望多貢獻點金額，這樣就可以讓紙幣數(shù)更少篷朵。區(qū)間覆蓋
假設(shè)我們有n個區(qū)別勾怒，區(qū)間的起始端點和結(jié)束端點分別是[l1，r1]声旺，[l2笔链，r2]，[l3腮猖，r3]鉴扫，.....，[ln澈缺，rn]坪创。我們從這n個區(qū)間中選出一部分區(qū)間炕婶，這部分區(qū)間滿足兩兩不相交（端點相交的情況不算相交），最多能選出多少個區(qū)間呢莱预？
解答：我們假設(shè)這n個區(qū)區(qū)間中最左端點是lmin柠掂，最右端點是rmax。這個問題就相當于依沮，我們選擇幾個不相交的區(qū)間涯贞，從左到右將[lmin，rmax]覆蓋上悉抵。我們按照起始端點從小到大的順序?qū)@n個區(qū)間排序肩狂。
我們每次選擇的時候，左端點跟前面的已經(jīng)覆蓋的區(qū)間不重合的姥饰，右端點又盡量小，這樣可以讓剩下的未覆蓋區(qū)間盡可能的大孝治，就可以放置更多的區(qū)間列粪。如何用貪心算法實現(xiàn)Huffman壓縮編碼？
試圖用這種不等長的編碼方法谈飒，來進一步增加壓縮的效率岂座。
轉(zhuǎn)化為：如何給不同頻率的字符選擇不同長度的編碼呢？
解答：我們可以把出現(xiàn)頻率比較多的字符杭措，用稍微短一些的編碼费什；出現(xiàn)頻率比較少的字符，用稍微長一些的編碼手素。
通過優(yōu)先級隊列實現(xiàn)（存放頻率）在一個非負整數(shù)a中鸳址，我們希望從中移除k個數(shù)字，讓剩下的數(shù)字值最小泉懦，如何選擇移除哪k個數(shù)字呢稿黍？
解答：由最高位開始，比較低一位數(shù)字崩哩，如高位大巡球，移除，若高位小邓嘹，則向右移一位繼續(xù)比較兩個數(shù)字酣栈，直到高位大于低位則移除，循環(huán)k次汹押。假設(shè)有n個人等待被服務(wù)矿筝，但是服務(wù)窗口只有一個，每個人需要被服務(wù)的時間長度是不同的鲸阻，如何安排被服務(wù)的先后順序跋涣，才能讓這n個人總的等待時間最短缨睡？
解答：由等待時間最短的開始服務(wù)
經(jīng)典應(yīng)用
- 霍夫曼編碼（Huffman Coding)
- Prim和Kruskal最小生成樹算法
- Dijkstra單源最短路徑算法。
