貪心算法

開放分類：算法、信息學(xué)

貪心算法

例題：畜棚修理（1999年USACO春季公開賽試題）

有一長列畜棚，其中一些被木板覆著。你可以使用總共N個木板，這些木板可以覆蓋任意連續(xù)的畜棚。覆蓋所有必要的畜棚，使得所用的木板盡可能的少。

貪心算法很快，一般的為O(n)到O(n^2)而且需要很少的額外空間。不幸地是，它一般是不正確的。但是，當它正確，它就會遠快于其它算法。

算法

在貪心算法背后所隱含的基本算法，是從小規(guī)模問題中生成大規(guī)模問題。這不像其他算法，在貪心算法的進行過程中，它只關(guān)心它發(fā)現(xiàn)的最好的策略。因此，對于例題，為了生成N=5時的策略，它先尋找N=4時的最優(yōu)策略，然后以此生成。此時，對于其它N=4時的策略，不予考慮。

問題
貪心時，有兩個基礎(chǔ)的問題需要考慮。

怎么生成？

怎樣從小規(guī)模策略中生成大規(guī)模策略？一般地，有這樣一個運作過程。對于例題，由四塊木板生成五塊木板的最顯然的方法，就是將其中一塊木板中的一部分拿掉，這樣一塊木板變成了兩塊。而你要做的，是在那些不需要被木板覆蓋的畜棚區(qū)域中，選出最長的片段（這樣，就使得所用的木板最少了）。

拿掉被覆蓋畜棚的木板中的一個片段，使得它變成兩段。一段在該片段之前，一段在該片段之后。

它有效嗎？

對于程序員，真正的挑戰(zhàn)是談心算法不總有效。即便它可能對于一些簡單的數(shù)據(jù)、隨意的數(shù)據(jù)，以及所有你能考慮到的情況有效，但只要有一種情況不奏效，至少一個（假設(shè)沒有更多），評測系統(tǒng)就會由此停下。

對于例題，看看上述的談心算法的工作工程，要考慮如下幾點：

假設(shè)，答案中不包括貪心算法所拿掉的較大缺口，而是較小的。那么通過結(jié)合較小缺口，使其與兩邊的木板相連。答案是通過用一定量的木板覆蓋盡量少的畜棚。新的答案更好些，所以假設(shè)是錯誤的，我們總是去掉最大缺口是正確的。

如果答案不包含特殊的缺口，但是包含一個與之同樣大的缺口，做相同的轉(zhuǎn)換，發(fā)現(xiàn)所需的木板量并沒有變化，這個新的答案與原來的答案是一樣的。我們可以選取任意一個。

因此，所產(chǎn)生的結(jié)果是最優(yōu)的，它包含的是最大的切除片段。每一步都是這樣，最終也一定是這樣。

結(jié)論

如果一個貪心算法存在，那就用它。它們的編寫、編譯、運行都很快，唯一令人遺憾地，它地正確性。如果貪心算法可以得到正確的答案，那就努力地尋找這個算法。但是，不要指望貪心算法能解決所有問題

貪心算法的3個相當經(jīng)典的程序

1.線段覆蓋（linescover）

題目大意：在一維空間中告訴你N條線段的起始坐標與終止坐標，要求求出這些線段一共占了多大的長度。

解題思路：將線段按其實坐標進行排序,使之依次遞增。然后定義一個變量last記錄考慮到當前線段之時被線段覆蓋的最大的坐標值。因為已經(jīng)排過序所以當前線段的效應(yīng)長度為(x為起始坐標，y為終止坐標)：

length:=0(y<=last)

y-last(x<=last &y>last)

y-x(x>last &y>last)

并且注意同時更新last的值。最后統(tǒng)計每條線段的效應(yīng)長度就為我們所需要的答案。

2.最優(yōu)數(shù)對（bestpair）

題目大意：按遞增的順序告訴你N個正整數(shù)和一個實數(shù)P，要求求出求出該數(shù)列中的比例最接近P的兩個數(shù)（保證絕對沒有兩個數(shù)使得其比值為P）。

解題思路：定義兩個指針i和j，然后進行如下操作：當code[j]/code[i]>p時inc（j），當code[j]/code[i]<p時inc（i），然后記錄其中產(chǎn)生的最優(yōu)值即可。

3.連續(xù)數(shù)之和最大值（maxsum）

題目大意：給你N個數(shù)，要求求出其中的連續(xù)數(shù)之和的最大值。（也可以加入a和b來限制連續(xù)數(shù)的長度不小于a且不大于b）。

解題思路：定義一個統(tǒng)計變量tot，然后用循環(huán)進行如下操作：inc（tot，item）其中如果出現(xiàn)tot<0的情況，則將tot賦值為0。在循環(huán)過程之中tot出現(xiàn)的最大值即為答案。如果加入了限制條件的話，問題就變得難一些了（這句真的不是廢話）。為此我們需要定義：數(shù)組sum[i]來表示code[1]到code[i]之和（這樣的話code[a]~code[b]的和我們就可以用sum[b]-sum[a-1]來表示了。），數(shù)組hash[i]來表示滿足條件的sum[a-1]所對應(yīng)的下標（并使之按sum[i]的遞增順序排列，一定要處理好sum[i]進出hash的過程）。這樣的話對于終止坐標為i的連續(xù)數(shù)列其最大和必定為sum[i]-sum[hash[1]],求出其最大值即可。

愛華網(wǎng)本文地址 » http://www.klfzs.com/a/25101010/35182.html