參考：http://blog.csdn.net/a925907195/article/details/41314549
一唯沮、基本概念
所謂貪心算法是指脖旱，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇介蛉。也就是說萌庆，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解币旧。
貪心算法沒有固定的算法框架践险，算法設(shè)計的關(guān)鍵是貪心策略的選擇。必須注意的是吹菱，貪心算法不是對所有問題都能得到整體最優(yōu)解巍虫，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以后的過程不會影響以前的狀態(tài)鳍刷，只與當(dāng)前狀態(tài)有關(guān)占遥。
所以對所采用的貪心策略一定要仔細(xì)分析其是否滿足無后效性。
</br>
二输瓜、貪心算法的基本思路
1.建立數(shù)學(xué)模型來描述問題筷频。
2.把求解的問題分成若干個子問題。
3.對每一子問題求解前痘，得到子問題的局部最優(yōu)解。
4.把子問題的解局部最優(yōu)解合成原來解問題的一個解担忧。
利用貪心算法解題芹缔，需要解決兩個問題：
- 一是問題是否適合用貪心法求解。我們看一個找?guī)诺睦悠渴ⅲ绻粋€貨幣系統(tǒng)有三種幣值最欠，面值分別為一角示罗、五分和一分，求最小找?guī)艛?shù)時芝硬，可以用貪心法求解蚜点；如果將這三種幣值改為一角一分、五分和一分拌阴，就不能使用貪心法求解绍绘。用貪心法解題很方便，但它的適用范圍很小迟赃，判斷一個問題是否適合用貪心法求解陪拘，目前還沒有一個通用的方法，在信息學(xué)競賽中纤壁，需要憑個人的經(jīng)驗來判斷左刽。
- 二是確定了可以用貪心算法之后，如何選擇一個貪心標(biāo)準(zhǔn)酌媒，才能保證得到問題的最優(yōu)解欠痴。在選擇貪心標(biāo)準(zhǔn)時，我們要對所選的貪心標(biāo)準(zhǔn)進(jìn)行驗證才能使用秒咨，不要被表面上看似正確的貪心標(biāo)準(zhǔn)所迷惑喇辽，
</br>
三、貪心算法的實現(xiàn)框架
從問題的某一初始解出發(fā)拭荤；
while （能朝給定總目標(biāo)前進(jìn)一步）
{
利用可行的決策茵臭，求出可行解的一個解元素；
}
由所有解元素組合成問題的一個可行解舅世；
</br>
四旦委、經(jīng)典例子
［均分紙牌］有N堆紙牌，編號分別為1雏亚，2缨硝，…，n罢低。每堆上有若干張,但紙牌總數(shù)必為n的倍數(shù).可以在任一堆上取若干張紙牌,然后移動查辩。移牌的規(guī)則為：在編號為1上取的紙牌，只能移到編號為2的堆上网持；在編號為n的堆上取的紙牌宜岛，只能移到編號為n-1的堆上；其他堆上取的紙牌功舀，可以移到相鄰左邊或右邊的堆上∑汲現(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多辟汰。例如：n=4列敲，4堆紙牌分別為：① 9 ② 8 ③ 17 ④ 6 移動三次可以達(dá)到目的：從③取4張牌放到④ 再從③區(qū)3張放到②然后從②去1張放到①阱佛。
輸入輸出樣例：4
9 8 17 6
屏幕顯示：3
算法分析：設(shè)a[i]為第I堆紙牌的張數(shù)（0<=I<=n），v為均分后每堆紙牌的張數(shù)戴而，s為最小移動次數(shù)凑术。
我們用貪心算法，按照從左到右的順序移動紙牌所意。如第I堆的紙牌數(shù)不等于平均值淮逊，則移動一次（即s加1），分兩種情況移動：
1．若a[i]>v扁眯，則將a[i]-v張從第I堆移動到第I+1堆壮莹；
2．若a[i]<v，則將v-a[i]張從第I+1堆移動到第I堆姻檀。
為了設(shè)計的方便命满，我們把這兩種情況統(tǒng)一看作是將a[i]-v從第I堆移動到第I+1堆，移動后有a[i]=v; a[I+1]=a[I+1]+a[i]-v.
在從第I+1堆取出紙牌補充第I堆的過程中可能回出現(xiàn)第I+1堆的紙牌小于零的情況绣版。
如n=3胶台，三堆指派數(shù)為1 2 27 ，這時v=10杂抽，為了使第一堆為10诈唬，要從第二堆移9張到第一堆，而第二堆只有2張可以移缩麸，這是不是意味著剛才使用貪心法是錯誤的呢铸磅？
我們繼續(xù)按規(guī)則分析移牌過程，從第二堆移出9張到第一堆后杭朱，第一堆有10張阅仔，第二堆剩下-7張，在從第三堆移動17張到第二堆弧械，剛好三堆紙牌都是10八酒，最后結(jié)果是對的，我們在移動過程中刃唐，只是改變了移動的順序羞迷，而移動次數(shù)不便，因此此題使用貪心法可行的画饥。
［最大整數(shù)］設(shè)有n個正整數(shù)衔瓮，將它們連接成一排，組成一個最大的多位整數(shù)抖甘。
例如：n=3時热鞍，3個整數(shù)13，312，343碍现，連成的最大整數(shù)為34331213。
又如：n=4時米奸，4個整數(shù)7昼接，13，4悴晰，246慢睡，連成的最大整數(shù)為7424613。
輸入：n
N個數(shù)
輸出：連成的多位數(shù)
算法分析：此題很容易想到使用貪心法铡溪，在考試時有很多同學(xué)把整數(shù)按從大到小的順序連接起來漂辐，測試題目的例子也都符合，但最后測試的結(jié)果卻不全對棕硫。按這種標(biāo)準(zhǔn)髓涯，我們很容易找到反例：12，121應(yīng)該組成12121而非12112哈扮，那么是不是相互包含的時候就從小到大呢纬纪？也不一定，如12滑肉，123就是12312而非12123包各，這種情況就有很多種了。是不是此題不能用貪心法呢靶庙？
其實此題可以用貪心法來求解问畅，只是剛才的標(biāo)準(zhǔn)不對，正確的標(biāo)準(zhǔn)是：先把整數(shù)轉(zhuǎn)換成字符串六荒，然后在比較a+b和b+a护姆，如果a+b>=b+a，就把a排在b的前面恬吕，反之則把a排在b的后面签则。
Leetcode典型題：
122 Best Time to Buy and Sell Stock II
134 Gas Station
402 Remove K Digits
