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

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

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

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

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

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

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

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

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

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