貪心算法（又稱貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。

貪心算法的基本思路是從問(wèn)題的某一個(gè)初始解出發(fā)一步一步地進(jìn)行，根據(jù)某個(gè)優(yōu)化測(cè)度，每一步都要確保能獲得局部最優(yōu)解。每一步只考慮一個(gè)數(shù)據(jù)，他的選取應(yīng)該滿足局部?jī)?yōu)化的條件。若下一個(gè)數(shù)據(jù)和部分最優(yōu)解連在一起不再是可行解時(shí)，就不把該數(shù)據(jù)添加到部分解中，直到把所有數(shù)據(jù)枚舉完，或者不能再添加算法停止。

排序：

貪心算法解決的是最優(yōu)值的問(wèn)題（即求最大值或最小值一類的問(wèn)題），因此，在求解局部最優(yōu)解時(shí)，一般需要對(duì)數(shù)據(jù)進(jìn)行從小到大（或者從大到?。┻M(jìn)行排序后再根據(jù)順序依次選擇做出局部最優(yōu)選擇。所以，很多的貪心題目，都需要對(duì)數(shù)據(jù)進(jìn)行排序。

無(wú)后效性：

貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無(wú)后效性，即某個(gè)狀態(tài)以前的過(guò)程不會(huì)影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。

最優(yōu)子結(jié)構(gòu)：

當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。運(yùn)用貪心策略在每一次轉(zhuǎn)化時(shí)都取得了最優(yōu)解。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用貪心算法或動(dòng)態(tài)規(guī)劃算法求解的關(guān)鍵特征。貪心算法的每一次操作都對(duì)結(jié)果產(chǎn)生直接影響，而動(dòng)態(tài)規(guī)劃則不是。貪心算法對(duì)每個(gè)子問(wèn)題的解決方案都做出選擇，不能回退；動(dòng)態(tài)規(guī)劃則會(huì)根據(jù)以前的選擇結(jié)果對(duì)當(dāng)前進(jìn)行選擇，有回退功能。動(dòng)態(tài)規(guī)劃主要運(yùn)用于二維或三維問(wèn)題，而貪心一般是一維問(wèn)題。

貪心算法的優(yōu)缺點(diǎn)：

貪心算法是很常見(jiàn)的算法之一，貪心策略一旦經(jīng)過(guò)證明成立后，它就是一種高效的算法。一般可以達(dá)到O(n)或者O（nlg(n)) (用到排序的話）的級(jí)別。

貪心算法的難點(diǎn)在于：你需要證明貪心策略的正確性后才能真正運(yùn)用到題目的算法中。

在解決最優(yōu)值的一類問(wèn)題時(shí)，如果你實(shí)在想不出正解，用用貪心有時(shí)也是可以拿到部分分的，在比賽里算是騙分算法之一。

貪心算法沒(méi)有固定的算法框架，基本靠自己的做題經(jīng)驗(yàn)和題目分析能力，所以這個(gè)算法需要多做題，積累經(jīng)驗(yàn)。

這個(gè)算法需要你自力更生了。