NOI導(dǎo)刊-貪心與分治

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

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

定義

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

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