貪心算法(1)講解學(xué)習(xí)

貪心(tānxīn)算法第一頁，共38頁。貪心方法的基本(jīběn)思想貪心是一種(yīzhǒnɡ)解題策略，也是一種(yīzhǒnɡ)解題思想使用貪心方法需要注意局部最優(yōu)與全局最優(yōu)的關(guān)系，選擇當(dāng)前狀態(tài)的局部最優(yōu)并不一定能推導(dǎo)出問題的全局最優(yōu)利用貪心策略解題，需要解決兩個問題：該題是否適合于用貪心策略求解如何選擇貪心標(biāo)準(zhǔn)，以得到問題的最優(yōu)解第二頁，共38頁?！疽吭谝粋€N×M的方格(fānɡɡé)陣中，每一格子賦予一個數(shù)（即為權(quán)），規(guī)定每次移動時只能向上或向右?，F(xiàn)試找出一條路徑，使其從左下角至右上角所經(jīng)過的權(quán)之和最大。我們以2×3的矩陣為例：若按貪心(tānxīn)策略求解，所得路徑為：1→3→4→6；若按動態(tài)規(guī)劃求解(qiújiě)，所得路徑為：1→2→10→6。第三頁，共38頁。貪心(tānxīn)法的特點1.貪心選擇性質(zhì)：算法中每一步選擇都是當(dāng)前看似最佳的選擇，這種選擇依賴于已做出的選擇，但不依賴于未做的選擇。2.最優(yōu)子結(jié)構(gòu)性質(zhì)：算法中每一次都取得了最優(yōu)解(即局部最優(yōu)解)，要保證(bǎozhèng)最后的結(jié)果最優(yōu)，則必須滿足全局最優(yōu)解包含局部最優(yōu)解。但并不是所有具有最優(yōu)子結(jié)構(gòu)的問題都可以用貪心策略求解。因為貪心往往是盲目的，需要使用更理性的方法——動態(tài)規(guī)劃（例如“0-1背包問題”與“部分背包問題”）第四頁，共38頁?！締栴}(wèntí)1】部分背包問題(wèntí)給定一個最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有Wi公斤(ɡōnɡjīn)，其商品價值為Vi元/公斤(ɡōnɡjīn)，編程確定一個裝貨方案，使得裝入卡車中的所有物品總價值最大?！痉治觥恳驗槊恳粋€物品都可以分割成單位塊，單位塊的利益越大，顯然總收益(shōuyì)越大，所以它局部最優(yōu)滿足全局最優(yōu)，可以用貪心法解答。方法如下：先將單位塊收益(shōuyì)按從大到小進(jìn)行排列，然后用循環(huán)從單位塊收益(shōuyì)最大的取起，直到不能取為止便得到了最優(yōu)解。第五頁，共38頁。【問題(wèntí)2】0/1背包問題(wèntí)給定一個最大載重量(zhòngliàng)為M的卡車和N種動物。已知第i種動物的重量(zhòngliàng)為Wi，其最大價值為Vi，設(shè)定M，Wi，Vi均為整數(shù)，編程確定一個裝貨方案，使得裝入卡車中的所有動物總價值最大。【分析(fēnxī)】按貪心法：每次選價格最大的裝載。很明顯有反例：設(shè)N=3,卡車最大載重量是100,三種動物A、B、C的重量分別是40,50,70,其對應(yīng)的總價值分別是80、100、150。第六頁，共38頁。貪心策略與其他(qítā)算法的區(qū)別1.貪心與遞推：與遞推不同的是，貪心法中推進(jìn)的每一步不是依據(jù)某一固定的遞推式，而是當(dāng)前(dāngqián)看似最佳的貪心決策，不斷的將問題歸納為更加小的相似的子問題。所以歸納、分析、選擇正確合適的貪心策略，是正確解決貪心問題的關(guān)鍵。2.貪心與動態(tài)規(guī)劃：與動態(tài)規(guī)劃不同的是，貪心是鼠目寸光；動態(tài)規(guī)劃是統(tǒng)攬全局。第七頁，共38頁。幾個簡單的貪心(tānxīn)例子第八頁，共38頁。貪心(tānxīn)策略第九頁，共38頁。例題(lìtí)1：刪數(shù)問題鍵盤輸入一個高精度的正整數(shù)n（n<=240位）,去掉其中任意s個數(shù)字(shùzì)后剩下的數(shù)字(shùzì)按照原來的次序?qū)⒔M成一個新的正整數(shù)。編程對給定的n和s,尋求一種方案,使得剩下組成的新數(shù)最小?！緲永斎搿?78543182914【樣例輸出】13第十頁，共38頁。分析(fēnxī)由于正整數(shù)n的有效位數(shù)最大可達(dá)240位，所以可以采用字符串類型來存儲n。那么，應(yīng)如何來確定該刪除哪s位呢？是不是只要刪掉最大的s個數(shù)字就可以了呢？為了盡可能地逼近目標(biāo)，我們(wǒmen)選取的貪心策略為：每一步總是選擇一個使剩下的數(shù)最小的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個數(shù)字，否則刪除第一個遞減區(qū)間的首字符。然后回到串首，按上述規(guī)則再刪除下一個數(shù)字。重復(fù)以上過程s次，剩下的數(shù)字串便是問題的解了。第十一頁，共38頁。例題2：排隊(páiduì)問題在一個(yīɡè)食堂，有n個人排隊買飯，每個人買飯需要的時間為Ti，請你找出一種排列次序，是每個人買飯的時間總和最小。第十二頁，共38頁?！舅悸伏c撥】由題意可知，本題可以采用的貪心策略為：將n個人排隊買飯的時間從小到大排序，再依次累加每人的買飯時間，即可得到最小的總和。由樣例可知，排好序后的數(shù)據(jù)為(1,3,5,7,9,11)，每個人的買飯時間如下：T1=1T2=T1+t2=1+3=4T3=T2+t3=4+5=9T4=T3+t4=9+7=16T5=T4+t5=16+9=25T6=T5+t6=25+11=36總時間T=T1+T2+T3+T4+T5+T6=91用反證法證明如下：假設(shè)一個不排好序的n個人也能得到最優(yōu)答案，比如把(1,3,5,7,9,11)中的3,5對調(diào)一下，得到的序列為(1,5,3,7,9,11)。對調(diào)后，3,5前后的1,7,9,11四個人的買飯時間不會有變化，關(guān)鍵的變化是3,5兩個人。這時，5這個人的買飯時間為1+5，3這個人的買飯時間變?yōu)?+5+3，此時兩個人的總買飯時間中，5被累加了2次，而原方案中是3被累加了2次，其他(qítā)一樣。由此，兩者相比較，可知有序的序列能得到最優(yōu)的方案。對于其他(qítā)位置的改變可以采用同樣的方法證明。用反證法證明時，關(guān)鍵是證明反例不成立，由此推出原方案是最優(yōu)的。第十三頁，共38頁。問題(wèntí)推廣：排隊打水問題(wèntí)有n個人排隊到r個水龍頭去打水，他們裝滿水桶的時間t1、t2…….tn為整數(shù)且各不相等，應(yīng)如何安排他們的打水順序(shùnxù)才能使他們總共花費(fèi)的時間最少？第十四頁，共38頁。例題(lìtí)3：打包某工廠生產(chǎn)出的產(chǎn)品都要被打包放入正四棱柱的盒子內(nèi)，所有盒子的高度為h，但地面(dìmiàn)尺寸不同，可以為1x1、2x2、3x3、4x4、5x5、6x6。如下圖所示。這些(zhèxiē)盒子將被放入高度為h，地面尺寸為6x6的箱子中。為了降低運(yùn)送成本，工廠希望盡量減少箱子的數(shù)量。如果有一個好算法，能使箱子的數(shù)量降到最低，這將給工廠節(jié)省不少的資金。請你編寫一個程序。第十五頁，共38頁。分析(fēnxī)第十六頁，共38頁。分析(fēnxī)第十七頁，共38頁。例題(lìtí)4:均分紙牌（NOIP2002）有N堆紙牌，編號分別為1,2,…,N。每堆上有若干張，但紙牌總數(shù)必為N的倍數(shù)。可以在任一堆上取若于張紙牌，然后移動。

移牌規(guī)則為：在編號為1堆上取的紙牌，只能移到編號為2的堆上；在編號為N的堆上取的紙牌，只能移到編號為N-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。

現(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多。

例如N=4，4堆紙牌數(shù)分別為：①9②8③17④6

移動3次可達(dá)到(dádào)目的：從③取4張牌放到④(981310)->從③取3張牌放到②(9111010)->從②取1張牌放到①(10101010）。第十八頁，共38頁。分析(fēnxī)：【試題分析】我們要使移動次數(shù)最少，就是要把浪費(fèi)(làngfèi)降至零。通過對具體情況的分析，可以看出在某相鄰的兩堆之間移動兩次或兩次以上，是一種浪費(fèi)(làngfèi)，因為我們可以把它們合并為一次或零次。【思路點撥】如果你想到把每堆牌的張數(shù)減去平均張數(shù)，題目就變成移動正數(shù)，加到負(fù)數(shù)中，使大家都變成0，那就意味著成功了一半！從第i堆移動-m張牌到第i+1堆，等價于從第i+1堆移動m張牌到第i堆,步數(shù)是一樣的。注意最左邊的0和最右邊的0不能算在內(nèi)，如0,0,1,-3,4,0,-1,0,0第十九頁，共38頁。擴(kuò)展(kuòzhǎn)1：若題目中的紙牌排成一個環(huán)狀，應(yīng)如何處理(chǔlǐ)呢？其中n<=1000。第二十頁，共38頁。擴(kuò)展(kuòzhǎn)2：有n個小朋友坐成一圈，每人有ai個糖果。每人只能給左右兩人傳遞糖果。每人每次傳遞一個糖果代價為1。求使所有人獲得(huòdé)均等糖果的最小代價?！緮?shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)n<=1000；對于100%的數(shù)據(jù)n<=1000000第二十一頁，共38頁。貪心的經(jīng)典(jīngdiǎn)應(yīng)用（一）、三個區(qū)間上的問題1、選擇不相交(xiāngjiāo)區(qū)間問題2、區(qū)間選點問題3、區(qū)間覆蓋問題（二）、兩個調(diào)度問題1、流水作業(yè)調(diào)度問題2、帶限期和罰款的單位時間任務(wù)調(diào)度（三）Huffman編碼（四）最優(yōu)合并問題第二十二頁，共38頁。1、選擇不相交區(qū)間(qūjiān)問題給定n個開區(qū)間(ai,bi)，選擇盡量(jǐnliàng)多個區(qū)間，使得這些區(qū)間兩兩沒有公共點?！舅惴▽崿F(xiàn)】首先按照b1<=b2<=…<=bn的順序排序，依次(yīcì)考慮各個活動，如果沒有和已經(jīng)選擇的活動沖突，就選；否則就不選。

貪心策略：取第一個區(qū)間；

【正確性】：如果不選b1，假設(shè)第一個選擇的是bi，則如果bi和b1不交叉則多選一個b1更劃算；如果交叉則把bi換成b1不影響后續(xù)選擇。第二十三頁，共38頁。例題(lìtí)5：活動安排設(shè)有n個活動的集合E={1,2,..,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi，且si<fi。如果選擇(xuǎnzé)了活動i，則它在半開時間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動i與活動j是相容的。也就是說，當(dāng)fi<=sj或fj>=si時，活動i與活動j相容。選擇(xuǎnzé)出由互相兼容的活動組成的最大集合。第二十四頁，共38頁。2、區(qū)間(qūjiān)選點問題給定(ɡěidìnɡ)n個閉區(qū)間[ai,bi]，在數(shù)軸上選盡量少的點，使得每個區(qū)間內(nèi)都至少有一個點（不同區(qū)間內(nèi)含的點可以是同一個）。【算法】：首先按照b1<=b2<=…<=bn排序。每次標(biāo)記當(dāng)前(dāngqián)區(qū)間的右端點X，并右移當(dāng)前(dāngqián)區(qū)間指針，直到當(dāng)前(dāngqián)區(qū)間不包含X，再重復(fù)上述操作。

貪心策略：取最后一個。第二十五頁，共38頁。例題(lìtí)6：種樹（NOIP模擬試題）一條街的一邊有幾座房子。因為環(huán)保原因居民想要在路邊種些樹。路邊的地區(qū)(dìqū)被分割成塊，并被編號為1..n。每個塊大小為一個單位尺寸并最多可種一棵樹。每個居民想在門前種些樹并指定了三個號碼b,e,t。這三個數(shù)表示該居民想在b和e之間最少種t棵樹。當(dāng)然，b<=e,居民必須保證在指定地區(qū)(dìqū)不能種多于地區(qū)(dìqū)被分割成塊數(shù)的樹，即要求t<=e-b+1。允許居民想種樹的各自區(qū)域可以交叉。出于資金短缺的原因,環(huán)保部門請你求出能夠滿足所有居民的要求,需要種樹的最少數(shù)量。第二十六頁，共38頁。3、區(qū)間覆蓋(fùgài)問題給n個閉區(qū)間[ai,bi]，選擇盡量少的區(qū)間覆蓋一條指定(zhǐdìng)線段[s,t]。本題的突破口仍然是區(qū)間包含(bāohán)和排序掃描，不過先要進(jìn)行一次預(yù)處理。每個區(qū)間在[s,t]外的部分都應(yīng)該預(yù)先被切掉，因為它們的存在是毫無意義的。在預(yù)處理后，在相互包含(bāohán)的情況下，小區(qū)間顯然不應(yīng)該考慮。第二十七頁，共38頁。把各區(qū)間按照a從小到大排序，若a相同，則b從大到小排序（自動處理掉區(qū)間包含）。注意：若區(qū)間1的起點大于s，則無解（因為其他區(qū)間的起點更大，不可能覆蓋到s點），否則選擇起點在s的最長區(qū)間[ai,bi]后，新的起點應(yīng)該設(shè)置為bi，并且忽略所有區(qū)間在bi之前的部分，就像預(yù)處理一樣(yīyàng)。雖然貪心策略比上題復(fù)雜，但是仍然只需要一次掃描，如下圖，s為當(dāng)前有效起點（此前部分已被覆蓋），則應(yīng)該選擇區(qū)間2。貪心思想：在某個時刻s，找一個(yīɡè)滿足a[i]>=s的b[i]的最大值即可。第二十八頁，共38頁。例題(lìtí)7：區(qū)間（SDOI2005）現(xiàn)給定n個閉區(qū)間[ai,bi]，1<=i<=n。這些區(qū)間的并可以表示為一些不相交的閉區(qū)間的并。你的任務(wù)就是(jiùshì)在這些表示方式中找出包含最少區(qū)間的方案。你的輸出應(yīng)該按照區(qū)間的升序排列。這里如果說兩個區(qū)間[a,b]和[c,d]是按照升序排列的，那么我們有a<b<=c<=d。

任務(wù)：讀入這些區(qū)間，計算滿足給定條件的不相交閉區(qū)間，并把這些區(qū)間按照升序輸出。第二十九頁，共38頁。練習(xí)試題(shìtí)：噴水裝置有一塊草坪，長為L，寬為w；在它的中心線上裝有n個點狀的噴水裝置，效果是讓以它為中心半徑為ri的圓被潤濕(rùnshī)，選擇盡量少的噴水裝置把整個草坪全部潤濕(rùnshī)。第三十頁，共38頁。1、流水作業(yè)調(diào)度(diàodù)問題第三十一頁，共38頁。分析(fēnxī)第三十二頁，共38頁。2、帶限期(xiànqī)和罰款的單位時間任務(wù)調(diào)度第三十三頁，共38頁。旅行家的預(yù)算(yùsuàn)一個旅行家想駕駛汽車以最少的費(fèi)用從一個城市到另一個城市（假設(shè)出發(fā)時油箱時空的）。給定兩個城市之間的距離D1、汽車油箱的容量C（以升為單位(dānwèi)）、每升汽油能行駛的距離D2、出發(fā)點每升汽油價格P和沿途加油站數(shù)N（N可以為零），油站i離出發(fā)點的距離Di、每升汽油價格Pi（i=1，2，……，N）。計算結(jié)果四舍五入至小數(shù)點后兩位。如果無法到達(dá)目的地，則輸出“NoSolution”。樣例：InputD1=275.6 C=11.9 D2=27.4 P=2.8 N=2油站號I離出發(fā)點的距離Di每升汽油價格Pi1102.02.92220.02.2Output26.95（該數(shù)據(jù)表示最小費(fèi)用）第三十四頁，共38頁。分析(fēnxī)：需要考慮如下問題：出發(fā)前汽車的油箱是空的，故汽車必須在起點（1號站）處加油。加多少油？汽車行程到第幾站開始加油，加多少油？可以(kěyǐ)看出，原問題需要解決的是在哪些油站加油和加多少油的問題。對于某個油站，汽車加油后到達(dá)下一加油站，可以(kěy