定義

貪心算法是指每一步都求最優(yōu)解，迭代求得可能是全局最優(yōu)解的算法。當(dāng)然局部最優(yōu)解可能不是全局最優(yōu)解，也可能是全局最優(yōu)解，這就要看選擇的貪心策略了。一般證明選擇的策略是正確的，可以使用數(shù)學(xué)歸納法來證明，一般證明較難，可以寫一個(gè)暴力的方式求得最優(yōu)解，然后試不同的貪心策略，看哪一種正確即可，這個(gè)就是對(duì)數(shù)器的思路。

對(duì)數(shù)器就是通過大量的測(cè)試數(shù)據(jù)來驗(yàn)證算法是否正確的方式。

對(duì)數(shù)器核心部件有兩個(gè)：

• 絕對(duì)正確的方法
• 能產(chǎn)生大量隨機(jī)樣例的隨機(jī)發(fā)生器

貪心算法舉例

開最多的會(huì)議

題目： 給定每一個(gè)會(huì)議開始的時(shí)間和結(jié)束的時(shí)間，怎么安排會(huì)議要求會(huì)

議室進(jìn)行的會(huì)議的場(chǎng)次最多。返回這個(gè)最多的會(huì)議場(chǎng)次。

貪心策略：根據(jù)哪個(gè)項(xiàng)目早結(jié)束安排哪個(gè)

代碼：

總結(jié)

貪心算法，因?yàn)槭且x一種局部最優(yōu)解，要么選最大值，要么選最小值。所以基本上貪心算法都可以使用到堆的結(jié)構(gòu)來解決。多做幾道貪心算法的題就有感覺了。