一．貪心算法的基本概念
當一個問題具有最優子結構性質時，我們會想到用動態規劃法去解它。但有時會有更簡單有效的算法。我們來看一個找硬幣的例子。假設有四種硬幣，它們的面值分別為二角五分、一角、五分和一分。現在要找給某顧客六角三分錢。這時，我們會不假思索地拿出2個二角五分的硬幣，1個一角的硬幣和3個一分的硬幣交給顧客。這種找硬幣方法與其他的找法相比，所拿出的硬幣個數是最少的。這裡，我們下意識地使用了這樣的找硬幣算法：首先選出一個面值不超過六角三分的最大硬幣，即二角五分；然後從六角三分中減去二角五分，剩下三角八分；再選出一個面值不超過三角八分的最大硬幣，即又一個二角五分，如此一直做下去。這個找硬幣的方法實際上就是貪心算法。顧名思義，貪心算法總是作出在當前看來是最好的選擇。也就是說貪心算法並不從整體最優上加以考慮，它所作出的選擇只是在某種意義上的局部最優選擇。當然，我們希望貪心算法得到的最終結果也是整體最優的。上面所說的找硬幣算法得到的結果就是一個整體最優解。找硬幣問題本身具有最優子結構性質，它可以用動態規劃算法來解。但我們看到，用貪心算法更簡單，更直接且解題效率更高。這利用了問題本身的一些特性。例如，上述找硬幣的算法利用了硬幣面值的特殊性。如果硬幣的面值改為一分、五分和一角一分3種，而要找給顧客的是一角五分錢。還用貪心算法，我們將找給顧客1個一角一分的硬幣和4個一分的硬幣。然而3個五分的硬幣顯然是最好的找法。雖然貪心算法不是對所有問題都能得到整體最優解，但對范圍相當廣的許多問題它能產生整體最優解。如圖的單源最短路徑問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優解，但其最終結果卻是最優解的很好的近似解。
三．算法分析
貪心算法並不總能求得問題的整體最優解。但對於活動安排問題，貪心算法greedyse—1ector卻總能求得的整體最優解，即它最終所確定的相容活動集合a的規模最大。我們可以用數學歸納法來證明這個結論。
事實上，設e={1，2，…，n}為所給的活動集合。由於正中活動按結束時間的非減序排列，故活動1具有最早的完成時間。首先我們要證明活動安排問題有一個最優解以貪心選擇開始，即該最優解中包含活動1。設 是所給的活動安排問題的一個最優解，且a中活動也按結束時間非減序排列，a中的第一個活動是活動k。若k=1，則a就是一個以貪心選擇開始的最優解。若k>1，則我們設 。由於f1≤fk，且a中活動是互為相容的，故b中的活動也是互為相容的。又由於b中活動個數與a中活動個數相同，且a是最優的，故b也是最優的。也就是說b是一個以貪心選擇活動1開始的最優活動安排。因此，我們證明了總存在一個以貪心選擇開始的最優活動安排方案。
進一步，在作了貪心選擇，即選擇了活動1後，原問題就簡化為對e中所有與活動1相容的活動進行活動安排的子問題。即若a是原問題的一個最優解，則a’=a—{i}是活動安排問題 的一個最優解。事實上，如果我們能找到e’的一個解b’，它包含比a’更多的活動，則將活動1加入到b’中將產生e的一個解b，它包含比a更多的活動。這與a的最優性矛盾。因此，每一步所作的貪心選擇都將問題簡化為一個更小的與原問題具有相同形式的子問題。對貪心選擇次數用數學歸納法即知，貪心算法greedyselector最終產生原問題的一個最優解。
四．貪心算法的基本要素
貪心算法通過一系列的選擇來得到一個問題的解。它所作的每一個選擇都是當前狀態下某種意義的最好選擇，即貪心選擇。希望通過每次所作的貪心選擇導致最終結果是問題的一個最優解。這種啟發式的策略並不總能奏效，然而在許多情況下確能達到預期的目的。解活動安排問題的貪心算法就是一個例子。下面我們著重討論可以用貪心算法求解的問題的一般特征。
對於一個具體的問題，我們怎麼知道是否可用貪心算法來解此問題，以及能否得到問題的一個最優解呢?這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中
我們看到它們一般具有兩個重要的性質：貪心選擇性質和最優子結構性質。
1．貪心選擇性質
所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。在動態規劃算法中，每步所作的選擇往往依賴於相關子問題的解。因而只有在解出相關子問題後，才能作出選擇。而在貪心算法中，僅在當前狀態下作出最好選擇，即局部最優選擇。然後再去解作出這個選擇後產生的相應的子問題。貪心算法所作的貪心選擇可以依賴於以往所作過的選擇，但決不依賴於將來所作的選擇，也不依賴於子問題的解。正是由於這種差別，動態規劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行,以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為一個規模更小的子問題。
對於一個具體問題，要確定它是否具有貪心選擇性質，我們必須證明每一步所作的貪心選擇最終導致問題的一個整體最優解。通常可以用我們在證明活動安排問題的貪心選擇性質時所采用的方法來證明。首先考察問題的一個整體最優解，並證明可修改這個最優解，使其以貪心選擇開始。而且作了貪心選擇後，原問題簡化為一個規模更小的類似子問題。然後，用數學歸納法證明，通過每一步作貪心選擇，最終可得到問題的一個整體最優解。其中，證明貪心選擇後的問題簡化為規模更小的類似子問題的關鍵在於利用該問題的最優子結構性質。
2．最優子結構性質
當一個問題的最優解包含著它的子問題的最優解時，稱此問題具有最優子結構性質。問題所具有的這個性質是該問題可用動態規劃算法或貪心算法求解的一個關鍵特征。在活動安排問題中，其最優子結構性質表現為：若a是對於正的活動安排問題包含活動1的一個最優解,則相容活動集合a’=a—{1}是對於e’={i∈e:si≥f1}的活動安排問題的一個最優解。
3．貪心算法與動態規劃算法的差異
貪心算法和動態規劃算法都要求問題具有最優子結構性質，這是兩類算法的一個共同點。但是，對於一個具有最優子結構的問題應該選用貪心算法還是動態規劃算法來求解?是不是能用動態規劃算法求解的問題也能用貪心算法來求解?下面我們來研究兩個經典的組合優化問題，並以此來說明貪心算法與動態規劃算法的主要差別。
