貪心算法必知的知識(shí)點(diǎn)
貪心算法（又稱貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇桑滩。也就是說(shuō)，不從整體最優(yōu)上加以考慮允睹，他所做出的是在某種意義上的局部最優(yōu)解运准。
貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇缭受，選擇的貪心策略必須具備無(wú)后效性胁澳，即某個(gè)狀態(tài)以前的過(guò)程不會(huì)影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)米者。
基本思路
建立數(shù)學(xué)模型來(lái)描述問(wèn)題韭畸；
把求解的問(wèn)題分成若干個(gè)子問(wèn)題；
對(duì)每一子問(wèn)題求解塘雳，得到子問(wèn)題的局部最優(yōu)解陆盘；
把子問(wèn)題的解局部最優(yōu)解合成原來(lái)解問(wèn)題的一個(gè)解。
案例分析
區(qū)間調(diào)度問(wèn)題（interval shecduling)
問(wèn)題描述：
這是《算法導(dǎo)論》上的例子败明，也是一個(gè)非常經(jīng)典的問(wèn)題隘马。有n個(gè)需要在同一天使用同一個(gè)教室的活動(dòng)a1,a2,…,an，教室同一時(shí)刻只能由一個(gè)活動(dòng)使用妻顶。每個(gè)活動(dòng)ai都有一個(gè)開始時(shí)間si和結(jié)束時(shí)間fi 酸员。一旦被選擇后，活動(dòng)ai就占據(jù)半開時(shí)間區(qū)間[si,fi)讳嘱。如果[si,fi]和[sj,fj]互不重疊幔嗦，ai和aj兩個(gè)活動(dòng)就可以被安排在這一天。該問(wèn)題就是要安排這些活動(dòng)使得盡量多的活動(dòng)能不沖突的舉行沥潭。例如下圖所示的活動(dòng)集合S邀泉，其中各項(xiàng)活動(dòng)按照結(jié)束時(shí)間單調(diào)遞增排序。
幾種貪心策略：
1.最早開始時(shí)間??
即用每個(gè)工作的開始時(shí)間進(jìn)行升序排列，在保證不沖突的情況下汇恤，每次選擇開始時(shí)間最小的情況庞钢。
2.最早結(jié)束時(shí)間
即用每個(gè)工作的結(jié)束時(shí)間進(jìn)行升序排列，在保證不沖突的情況下（仍然考慮下一次的結(jié)束時(shí)間盡可能的小因谎，且下一次的開始時(shí)間需要大于上一次的結(jié)束時(shí)間）基括，每次選擇結(jié)束時(shí)間最小的情況。（上圖）
3.最少的運(yùn)行時(shí)間
即每一個(gè)工作的結(jié)束時(shí)間減去開始時(shí)間得到運(yùn)行時(shí)間财岔，并且在不沖突的情況下风皿，每次選擇運(yùn)行時(shí)間最短的工作。
4.最少?zèng)_突情況
即首先計(jì)算出當(dāng)前的工作i匠璧，它的沖突個(gè)數(shù)為k[i]桐款，用k[i]進(jìn)行上升排序。每次選擇沖突最小的情況患朱。
哪種策略下能得到最優(yōu)解鲁僚？答：最早結(jié)束時(shí)間
?證明方法：構(gòu)造法（深灰表選中的工作，淺灰表示反例）
最早開始時(shí)間：假設(shè)最早開始時(shí)間的工作的運(yùn)行時(shí)間很長(zhǎng)裁厅，就不是最優(yōu)。
最少運(yùn)行時(shí)間：假設(shè)最少運(yùn)行時(shí)間的的那個(gè)工作的結(jié)束時(shí)間很晚侨艾，就不是最優(yōu)执虹。
最少?zèng)_突：按上圖的情況，首先會(huì)選到深灰唠梨，然后再選擇旁邊的淺灰袋励，總共只有三個(gè)工作被選中，不是最優(yōu)当叭。
接著證明最早結(jié)束時(shí)間是最優(yōu)的（可以用歸納法）
算法思想：
????????????1.先按完成時(shí)間上升排序
? ? ? ? ? ? 2.選擇當(dāng)前的結(jié)束時(shí)間的最早的工作茬故，判斷該工作的開始時(shí)間是否滿足大于上一個(gè)工作的結(jié)束時(shí)間
? ? ? ? ? ? 3.如果不滿足，則尋找下一個(gè)蚁鳖，滿足的話重復(fù)2步磺芭，就選擇，直到遍歷完
總結(jié)而言就是：先排序醉箕，不沖突就選擇加入A（被選擇的job）钾腺，沖突就丟棄并遍歷下一個(gè)，最后返回A
實(shí)現(xiàn)：http://www.reibang.com/p/89f8c67b2a04
錢幣找零問(wèn)題
問(wèn)題描述：這個(gè)問(wèn)題在我們的日常生活中就更加普遍了讥裤。假設(shè)1元放棒、2元、5元己英、10元间螟、20元、50元、100元的紙幣分別有c0, c1, c2, c3, c4, c5, c6張∠崞疲現(xiàn)在要用這些錢來(lái)支付K元邮府，至少要用多少?gòu)埣垘牛坑秘澬乃惴ǖ乃枷敫绒龋茱@然褂傀，每一步盡可能用面值大的紙幣即可。在日常生活中我們自然而然也是這么做的加勤。
貪心策略：
最大面值：在程序中已經(jīng)事先將Value按照從大到小的順序排好仙辟。
算法思想：1.首先將面值從大到小排序 2.計(jì)算K/V的取低值為n，記錄n鳄梅，并求得剩余的K叠国，重復(fù)2過(guò)程，直到K的取值為零戴尸。
背包問(wèn)題
問(wèn)題描述：有一個(gè)背包粟焊，背包容量是M=150。有7個(gè)物品孙蒙，物品可以分割成任意大小项棠。要求盡可能讓裝入背包中的物品總價(jià)值V最大，但不能超過(guò)總?cè)萘縈挎峦。
貪心策略：
最大價(jià)值：在保證不超重的情況下香追，每次選擇價(jià)值最大的物品。
結(jié)果：DBFE 不是最優(yōu)
最小容量：在保證不超重的情況下坦胶，每次選擇重量最小的物品透典。
結(jié)果：FGBAE 不是最優(yōu)
最大單位容量的價(jià)值：選擇單位容量下，價(jià)值最大的那一個(gè)顿苇。
結(jié)果：FBGD 40+40+30+50
算法思想：
1.按單位容量的價(jià)值由大到小排序
2.如果不超重峭咒，就選擇，超重就舍棄纪岁。
實(shí)現(xiàn)：http://www.reibang.com/p/50f1d4e0555c
最小生成樹問(wèn)題
問(wèn)題描述：
求一個(gè)連通無(wú)向圖的最小生成樹的代價(jià)（圖邊權(quán)值為正整數(shù)）凑队。
Kruskal算法簡(jiǎn)述
假設(shè) WN=(V,{E}) 是一個(gè)含有 n 個(gè)頂點(diǎn)的連通網(wǎng)，則按照克魯斯卡爾算法構(gòu)造最小生成樹的過(guò)程為：先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)蜂科，而邊集為空的子圖顽决，若將該子圖中各個(gè)頂點(diǎn)看成是各棵樹上的根結(jié)點(diǎn)，則它是一個(gè)含有 n 棵樹的一個(gè)森林导匣。之后才菠，從網(wǎng)的邊集 E 中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹贡定，則將其加入子圖赋访，也就是說(shuō)，將這兩個(gè)頂點(diǎn)分別所在的兩棵樹合成一棵樹；反之蚓耽，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹上渠牲，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之步悠。依次類推签杈，直至森林中只有一棵樹，也即子圖中含有 n-1條邊為止鼎兽。
模擬過(guò)程：http://www.reibang.com/p/50f1d4e0555c
算法難點(diǎn)：
（1）邊的選擇要求從小到大選擇答姥，則開始顯然要對(duì)邊進(jìn)行升序排序。
（2）選擇的邊是否需要谚咬，則從判斷該邊加入后是否構(gòu)成環(huán)入手鹦付。
算法設(shè)計(jì)：
（1）對(duì)邊升序排序
在此采用鏈?zhǔn)浇Y(jié)構(gòu)，通過(guò)插入排序完成择卦。每一結(jié)點(diǎn)存放一條邊的左右端點(diǎn)序號(hào)敲长、權(quán)值及后繼結(jié)點(diǎn)指針
（2）邊的加入是否構(gòu)成環(huán)
一開始假定各頂點(diǎn)分別為一組，其組號(hào)為端點(diǎn)序號(hào)秉继。選擇某邊后祈噪，看其兩個(gè)端點(diǎn)是否在同一組中，即所在組號(hào)是否相同秕噪，如果是钳降，表示構(gòu)成了環(huán)，則舍去腌巾。? 如果兩個(gè)端點(diǎn)所在的組不同，則表示可以加入铲觉，則將該邊兩端的組合并成同一組澈蝙。
