貪心法的基本思路：
從問(wèn)題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。
該算法存在問(wèn)題：
1. 不能保證求得的最后解是最佳的；
2. 不能用來(lái)求最大或最小解問(wèn)題；
3. 只能求滿足某些約束條件的可行解的范圍。
實(shí)現(xiàn)該算法的過(guò)程：
從問(wèn)題的某一初始解出發(fā)；
while 能朝給定總目標(biāo)前進(jìn)一步 do
求出可行解的一個(gè)解元素；
由所有解元素組合成問(wèn)題的一個(gè)可行解
貪心算法最經(jīng)典的例子，給錢(qián)問(wèn)題。
比如中國(guó)的貨幣，只看元，有1元2元5元10元20、50、100
如果我要16元，可以拿16個(gè)1元，8個(gè)2元，但是怎么最少呢？
如果用貪心算，就是我每一次拿那張可能拿的最大的。
比如16，我第一次拿20拿不起，拿10元，OK，剩下6元，再拿個(gè)5元，剩下1元
也就是3張 10、5、1。
每次拿能拿的最大的，就是貪心。
但是一定注意，貪心得到的并不是最優(yōu)解，也就是說(shuō)用貪心不一定是拿的最少的張數(shù)
貪心只能得到一個(gè)比較好的解，而且貪心算法很好想得到。
再注意，為什么我們的錢(qián)可以用貪心呢？因?yàn)槲覀儑?guó)家的錢(qián)的大小設(shè)計(jì)，正好可以使得貪心算法算出來(lái)的是最優(yōu)解（一般是個(gè)國(guó)家的錢(qián)幣都應(yīng)該這么設(shè)計(jì)）。如果設(shè)計(jì)成別的樣子情況就不同了
比如某國(guó)的錢(qián)幣分為 1元3元4元
如果要拿6元錢(qián) 怎么拿？貪心的話 先拿4 再拿兩個(gè)1 一共3張錢(qián)
實(shí)際最優(yōu)呢？ 兩張3元就夠了
求最優(yōu)解的問(wèn)題，從根本上說(shuō)是一種對(duì)解空間的遍歷。最直接的暴力分析容易得到，最優(yōu)解的解空間通常都是以指數(shù)階增長(zhǎng)，因此暴力窮舉都是不可行的。
最優(yōu)解問(wèn)題大部分都可以拆分成一個(gè)個(gè)的子問(wèn)題，把解空間的遍歷視作對(duì)子問(wèn)題樹(shù)的遍歷，則以某種形式對(duì)樹(shù)整個(gè)的遍歷一遍就可以求出最優(yōu)解，如上面的分析，這是不可行的。
貪心和動(dòng)態(tài)規(guī)劃本質(zhì)上是對(duì)子問(wèn)題樹(shù)的一種修剪。兩種算法要求問(wèn)題都具有的一個(gè)性質(zhì)就是“子問(wèn)題最優(yōu)性”。即，組成最優(yōu)解的每一個(gè)子問(wèn)題的解，對(duì)
于這個(gè)子問(wèn)題本身肯定也是最優(yōu)的。如果以自頂向下的方向看問(wèn)題樹(shù)（原問(wèn)題作根），則，我們每次只需要向下遍歷代表最優(yōu)解的子樹(shù)就可以保證會(huì)得到整體的最優(yōu)
解。形象一點(diǎn)說(shuō)，可以簡(jiǎn)單的用一個(gè)值（最優(yōu)值）代表整個(gè)子樹(shù)，而不用去求出這個(gè)子樹(shù)所可能代表的所有值。
動(dòng)態(tài)規(guī)劃方法代表了這一類問(wèn)題的一般解法。我們自底向上（從葉子向根）構(gòu)造子問(wèn)題的解，對(duì)每一個(gè)子樹(shù)的根，求出下面每一個(gè)葉子的值，并且以其中
的最優(yōu)值作為自身的值，其它的值舍棄。動(dòng)態(tài)規(guī)劃的代價(jià)就取決于可選擇的數(shù)目（樹(shù)的叉數(shù)）和子問(wèn)題的的數(shù)目（樹(shù)的節(jié)點(diǎn)數(shù)，或者是樹(shù)的高度？）。
貪心算法是動(dòng)態(tài)規(guī)劃方法的一個(gè)特例。貪心特在，可以證明，每一個(gè)子樹(shù)的根的值不取決于下面葉子的值，而只取決于當(dāng)前問(wèn)題的狀況。換句話說(shuō)，不需
要知道一個(gè)節(jié)點(diǎn)所有子樹(shù)的情況，就可以求出這個(gè)節(jié)點(diǎn)的值。通常這個(gè)值都是對(duì)于當(dāng)前的問(wèn)題情況下，顯而易見(jiàn)的“最優(yōu)”情況。因此用“貪心”來(lái)描述這個(gè)算法的
本質(zhì)。由于貪心算法的這個(gè)特性，它對(duì)解空間樹(shù)的遍歷不需要自底向上，而只需要自根開(kāi)始，選擇最優(yōu)的路，一直走到底就可以了。這樣，與動(dòng)態(tài)規(guī)劃相比，它的代
價(jià)只取決于子問(wèn)題的數(shù)目，而選擇數(shù)目總為1。