1、貪心方法的基本思想 貪心是一種解題策略，也是一種解題思想 使用貪心方法需要注意局部最優與全局最優的關系，選擇當前狀態的局部最優并不一定能推導出問題的全局最優 利用貪心策略解題，需要解決兩個問題： 該題是否適合于用貪心策略求解 如何選擇貪心標準，以得到問題的最優解 【引例引例】在一個NM的方格陣中，每一格子賦予一個數（即為權），規定每次移動時只能向上或向右?，F試找出一條路徑，使其從左下角至右上角所經過的權之和最大。 我們以23的矩陣為例：若按貪心策略貪心策略求解，所得路徑為：1346；若按動態規劃動態規劃求解，所得路徑為：12106。貪心法的特點貪心法的特點 1.貪心選擇性質：貪心選擇性質：算法

2、中每一步選擇都是當前看似最佳的選擇，這種選擇依賴于已做出的選擇，但不依賴于未做的選擇。 2.最優子結構性質：最優子結構性質：算法中每一次都取得了最優解(即局部最優解)，要保證最后的結果最優，則必須滿足全局最優解包含局部最優解。 但并不是所有具有最優子結構的問題都可以用貪心策略求解。因為貪心往往是盲目的，需要使用更理性的方法動態規劃（例如“0-1背包問題”與“部分背包問題”）【問題問題1】部分背包問題部分背包問題 給定一個最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有Wi公斤，其商品價值為Vi元/公斤，編程確定一個裝貨方案，使得裝入卡車中的所有物品總價值最大。【分

3、析分析】因為每一個物品都可以分割成單位塊，單位塊的利益越大，顯然總收益越大，所以它局部最優滿足全局最優，可以用貪心法解答。 方法如下：先將單位塊收益按從大到小進行排列，然后用循環從單位塊收益最大的取起，直到不能取為止便得到了最優解?！締栴}問題2】0/1背包問題背包問題 給定一個最大載重量為M的卡車和N種動物。已知第i種動物的重量為Wi，其最大價值為Vi，設定M，Wi，Vi均為整數，編程確定一個裝貨方案，使得裝入卡車中的所有動物總價值最大。【分析分析】按貪心法：每次選價格最大的裝載。很明顯有反例：設N=3,卡車最大載重量是100,三種動物A、B、C的重量分別是40,50,70,其對應的總價值分別

4、是80、100、150。貪心策略與其他算法的區貪心策略與其他算法的區別別 1.貪心與遞推：貪心與遞推：與遞推不同的是，貪心法中推進的每一步不是依據某一固定的遞推式，而是當前看似最佳的貪心決策，不斷的將問題歸納為更加小的相似的子問題。所以歸納、分析、選擇正確合適的貪心策略，是正確解決貪心問題的關鍵。 2.貪心與動態規劃：貪心與動態規劃：與動態規劃不同的是，貪心是鼠目寸光；動態規劃是統攬全局。幾個簡單的貪心例子幾個簡單的貪心例子 例題例題1：刪數問題：刪數問題 鍵盤輸入一個高精度的正整數n（n從取3張牌放到(9 11 10 10)-從取1張牌放到(10 10 10 10）。 【試題分析試題分析】我

5、們要使移動次數最少，就是要把浪費降至零。通過對具體情況的分析，可以看出在某相鄰的兩堆之間移動兩次或兩次以上，是一種浪費，因為我們可以把它們合并為一次或零次。 【思路點撥思路點撥】如果你想到把每堆牌的張數減去平均張數，題目就變成移動正數，加到負數中，使大家都變成0，那就意味著成功了一半！ 從第i堆移動-m張牌到第i+1堆，等價于從第i+1堆移動m張牌到第i堆,步數是一樣的。 注意最左邊的0和最右邊的0不能算在內，如0,0,1,-3,4,0,-1,0,0 若題目中的紙牌排成一個環狀，應如何處理呢？ 其中n=1000。 有n個小朋友坐成一圈，每人有ai個糖果。每人只能給左右兩人傳遞糖果。每人每次傳遞

6、一個糖果代價為1。求使所有人獲得均等糖果的最小代價。 【數據規模數據規模】 對于30%的數據n=1000； 對于100%的數據n=1000000 貪心的經典應用貪心的經典應用 （一）、三個區間上的問題（一）、三個區間上的問題 1、選擇不相交區間問題、選擇不相交區間問題 2、區間選點問題、區間選點問題 3、區間覆蓋問題、區間覆蓋問題（二）、兩個調度問題（二）、兩個調度問題 1、流水作業調度問題、流水作業調度問題 2、帶限期和罰款的單位時間任務調度、帶限期和罰款的單位時間任務調度（三）（三）Huffman編碼編碼 （四）最優合并問題最優合并問題 給定給定n個開區間個開區間(ai, bi)，選擇盡量

7、多個區間，使，選擇盡量多個區間，使得這些區間兩兩沒有公共點。得這些區間兩兩沒有公共點。【算法實現算法實現】首先按照b1=b2=bn的順序排序，依次考慮各個活動，如果沒有和已經選擇的活動沖突，就選；否則就不選?！菊_性正確性】：如果不選b1，假設第一個選擇的是bi，則如果bi和b1不交叉則多選一個b1更劃算；如果交叉則把bi換成b1不影響后續選擇。 設有設有n個活動的集合個活動的集合E=1,2,.,n，其中每個活動，其中每個活動都要求使用同一資源，如演講會場等，而在同一都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動時間內只有一個活動能使用這一資源。每個活動i

8、都有一個要求使用該資源的起始時間都有一個要求使用該資源的起始時間si和一個結和一個結束時間束時間fi，且，且sifi。如果選擇了活動。如果選擇了活動i，則它在半，則它在半開時間區間開時間區間si,fi)內占用資源。若區間內占用資源。若區間si,fi)與區與區間間sj,fj)不相交，則稱活動不相交，則稱活動i與活動與活動j是相容的。是相容的。也就是說，當也就是說，當fi=si時，活動時，活動i與活動與活動j相相容。選擇出由互相兼容的活動組成的最大集合。容。選擇出由互相兼容的活動組成的最大集合。 給定給定n個閉區間個閉區間ai, bi，在數軸上選盡量少的，在數軸上選盡量少的點，使得每個區間內都至少

9、有一個點（不同區點，使得每個區間內都至少有一個點（不同區間內含的點可以是同一個）。間內含的點可以是同一個）?！舅惴ㄋ惴ā浚菏紫劝凑誦1=b2=bn排序。每次標記當前區間的右端點X，并右移當前區間指針，直到當前區間不包含X，再重復上述操作。例題例題6：種樹（：種樹（NOIP模擬模擬試題）試題） 一條街的一邊有幾座房子。因為環保原因居民想要在路邊種些樹。路邊的地區被分割成塊，并被編號為1.n。每個塊大小為一個單位尺寸并最多可種一棵樹。每個居民想在門前種些樹并指定了三個號碼b,e,t。這三個數表示該居民想在b和e之間最少種t棵樹。當然，b=e,居民必須保證在指定地區不能種多于地區被分割成塊數的樹，即

10、要求t=s的的bi的最大值即可。的最大值即可。 例題例題7：區間（：區間（SDOI2005） 現給定n個閉區間ai,bi，1=i=n。這些區間的并可以表示為一些不相交的閉區間的并。你的任務就是在這些表示方式中找出包含最少區間的方案。你的輸出應該按照區間的升序排列。這里如果說兩個區間a, b和c, d是按照升序排列的，那么我們有ab=c=d。 任務：讀入這些區間，計算滿足給定條件的不相交閉區間，并把這些區間按照升序輸出。 練習試題：噴水裝置練習試題：噴水裝置 有一塊草坪，長為L，寬為w；在它的中心線上裝有n個點狀的噴水裝置，效果是讓以它為中心半徑為ri的圓被潤濕，選擇盡量少的噴水裝置把整個草坪全

11、部潤濕。 旅行家的預算 一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設出發時油箱時空的）。給定兩個城市之間的距離D1、汽車油箱的容量C（以升為單位）、每升汽油能行駛的距離D2、出發點每升汽油價格P和沿途加油站數N（N可以為零），油站i離出發點的距離Di、每升汽油價格Pi（i=1，2，N）。 計算結果四舍五入至小數點后兩位。 如果無法到達目的地，則輸出“No Solution”。 樣例： Input D1=275.6 C=11.9D2=27.4 P=2.8 N=2 油站號I離出發點的距離Di每升汽油價格Pi1102.02.92220.02.2 Output 26.95（該數據表示最

12、小費用）分析： 需要考慮如下問題： 出發前汽車的油箱是空的，故汽車必須在起點（1號站）處加油。加多少油？ 汽車行程到第幾站開始加油，加多少油？ 可以看出，原問題需要解決的是在哪些油站加油和加多少油的問題。對于某個油站，汽車加油后到達下一加油站，可以歸結為原問題的子問題。因此，原問題關鍵在于如何確定下一個加油站。通過分析，我們可以選擇這樣的貪心標準： 對于加油站I，下一個加油站J可能第一個是比油站I油價便宜的油站，若不能到達這樣的油站，則至少需要到達下一個油站后，繼續進行考慮。 對于第一種情況，則油箱需要（d（j）-d（i）/m加侖汽油。對于第二種情況，則需將油箱加滿。算法 I := 1 汽車出發設定為第1個加油站L := C*D2； 油箱裝滿油能行駛的距離repeat 在L距離以內，向后找第一個油價比I站便宜的加油站J； if J存在 then if I站剩余油能到達J then 計算到達J站的剩油 else 在I站購買油，使汽車恰好能到達J站 else 在I站加滿油； I :=