貪心與分治長沙市第一中學曹利國貪心方法按照當前的狀態，選擇最好的決策，這就是貪心法。在實際的應用中，人們往往不可能精確計算出怎樣才是最好的決策，只能憑借往常的經驗，保證每一步都是最好的選擇。在解題的過程中，這樣的算法一般是比較容易想到并且易于編程實現的。能夠使用貪心算法解決的問題，必然是每次都進行最優的選擇，并且通過證明其得到的最后結果也是最優的。反之，如果不能證明每次進行最優選擇后，最終會得到最優的結果，就不能使用貪心算法。其實，大局部的問題都是不能使用貪心算法的，簡單的例子：現有10元、7元、2元、1元四種紙幣，使用的張數不限，需要用這四種紙幣湊成p元錢，怎樣用最少的張數到達此要求。此題我們很容易就想到了貪心的算法，即每次盡量選面值大的紙幣。但是，在p=14時，貪心算法的結果為14=10+2+2，而最優結果為14=7+7，貪心顯然是不對的。然而，如果我們將其中的7元紙幣換成5元紙幣，貪心算法卻又是對的。這就需要我們用證明來判斷了。例題1罰款問題 現有一臺機器以及n項要完成的工作，該機器每完成一項工作需要1的單位時間，而工作i如果沒有在t[i]的時間內完成，將會受到c[i]的罰款。求怎樣安排工作的順序，使完成工作后總的罰款數最少。分析要使罰款最少，我們顯然應盡量完成c[i]值較大的工作。此時，我們可以將工作按c[i]從大到小進行排序，然后按照排好的順序依次對工作進行安排，安排的規那么為：使處理工作i的時間既在t[i]之內，又盡量靠后；如果t[i]之內的時間都已經排滿，就放棄處理此項工作。

證明假設按照上述方法得到的解不是最優的，那么必然存在某個工作j應當安排到處理的過程中，卻沒有得到安排。假設我們要將該工作安排進去，由于時間t[j]內都已經排滿，就必然需要將一個已安排的工作k與之替換，而c[k]>=c[j]，這樣替換顯然會增加罰款的數額。因此，除上述安排方法以外的安排方法都不會使罰款的數額減少，可得上述方法得到的結果是最優的。例題2：INT〔整數區間〕

定義

一個整數區間[A，B]，A﹤B，是一個從A開始，至B結束的連續整數的集合。任務是從文件中讀取區間的個數及其對它們的描述，找出滿足下述條件的所含元素個數最少的集合中元素的個數：對于每一個區間，都至少有兩個不同的整數屬于該集合。輸入：文本文件INT.IN的首行包括區間的數目N，1≦N≦10000。接下來的N行，每行包括兩個整數A，B，被一空格隔開，0≦A≦B≦10000，它們是某一個區間的開始值和結束值。輸出：最少元素數目。例如輸入：436240247輸出：4分析此題“會場安排”問題十分相似，可以用同樣的貪心方法：按照所有區間的結束位置排序，結束位置相同的項，開始位置小的項在前。從區間1到區間n進行循環，對于當前區間，假設集合中的數不能覆蓋它，那么從區間末尾向前掃描，假設當前數未在集合中出現，那么將該數參加集合，直至使集合能覆蓋該區間為止。例如：【0，1，2】【2，3，4】【3，4，5，6】【4，5，6，7】【】【2】【2,1】【2,1,4】【2,1,4,6】上述算法的指導思想是在某一區間中排列越靠后的數對以后區間的影響越大，即它在以后區間出現的可能性越大，但未經嚴格數學證明

具體實現由于pascal規定的集合類型只有[0..255]，因此在實現時不能使用集合作數據結構，用數組直接保存也不行，因為在數組中查找數據相當費時，注意到每個區間中的數大小不超過10000，可用一個下標為[0..10000]的布爾型數組標記該數是否出現過，從而解決這一問題。例題3：零件分組某工廠生產一批棍狀零件，每個零件都有一定的長度〔Li〕和重量〔Wi〕。現在為了加工需要，要將它們分成假設干組，使每一組的零件都能排成一個長度和重量都不下降〔假設i<j，那么Li<=Lj，Wi<=Wj〕的序列。請問至少要分成幾組?輸入：第一行為一個整數N〔N<=1000〕，表示零件的個數。第二行有N對正整數，每對正整數表示這些零件的長度和重量，長度和重量均不超過10000。輸出：僅一行，即最少分成的組數。樣例〔STICK.IN〕58438239735STICK.OUT2例題4：乘船問題〔ＨＮＣＯＩ〕 有N個人需要乘船，而每船最多只能載兩人，且必須同名或同姓。求最少需要多少條船。問題分析看到這道題，很多人都會想到圖的數據結構：將N個人看作無向圖的N個點，凡同名或同姓的人之間都連上邊。要滿足用船最少的條件，就是需要盡量多的兩人共乘一條船，表現在圖中就是要用最少的邊完成對所有頂點的覆蓋。這就正好對應了圖論的典型問題：求最小邊的覆蓋。所用的算法為“求任意圖最大匹配”的算法。分析使用“求任意圖最大匹配”的算法比較復雜(要用到擴展交錯樹，對花的收縮等等)，效率也不是很高。因此，我們必須尋找一個更簡單高效的方法。 首先，由于圖中任兩個連通分量都是相對獨立的，也就是說任一條匹配邊的兩頂點，都只屬于同一個連通分量。因此，我們可以對每個連通分量分別進行處理，而不會影響最終的結果。同時，我們還可以對需要船只s的下限進行估計：對于一個包含Pi個頂點的連通分量，其最小覆蓋邊數顯然為[Pi/2]。假設圖中共有L個連通分量，那么s=∑[Pi/2](1<=i<=L)。 然后，我們通過屢次嘗試，可得出一個猜測： 實際需要的覆蓋邊數完全等于我們求出的下限∑[Pi/2](1<=i<=L)。采用圖的數據結構得出的算法為：每次輸出一條非橋的邊，并從圖中將邊的兩頂點刪去。此算法的時間復雜度為O(n3)。〔尋找一條非橋邊的復雜度為O(n2)，尋找覆蓋邊操作的復雜度為O(n)〕采用樹結構解決見文檔例題５：通訊保衛戰見文本例題６：猜數游戲猜數游戲是一個古老的智力游戲。一個游戲者A首先想出一個數x〔1xn〕，讓另一個游戲者B來猜