最佳解? 這種解答是許多問題所追尋的目標．例如，在一個城市裡找到出發點和目的地的最短距離．直覺來看，若你沒有把所有可能的路徑列出來，你怎麼知道那一個才是最短的．再舉例一個例子，在一個 int array 裡面，找出最大值的元素位置．若你沒把所有的元素都拜訪一遍，你怎知道那一個才是最大的．這兩個例子雖然都是在找 "最佳解"，但是解法的思考卻不太一樣．第二個例子的思考是 "一條路"，而第一個例子是 "多條絡"．在 "一條路" 的情況下，對下一個步驟來說沒什麼好選擇的，只能一直往前走．然而，"多條路"的情況下，在什麼路口選擇什麼路，這對答案或執行過程會有很大的影響．
前面已有兩篇文章簡單地介紹了貪心方法．這篇文章要討論的是利用貪心方法得到的解答會是最佳解嗎 ? 用一個簡單的問題來測試．假設郵局提供的郵票面值如下:
$10, $5, $2, $1, $0.5, $0.2, $0.1
現在你要寄一封信，它所需的郵資是16.1 元，請問最少要用幾張郵票 ? 這是一個最佳解的問題，目的是要找最少的郵票數量. 使用貪心方法來解這問題，它所需的程式碼如下:
以上的程式範例就是一個貪心方法．從最大的面值一直嘗試到最小的面值，一直湊到超過所需要賺買的郵票面值. 得到的答案是 $10, $5, $1, $0.1，需要四張郵票，面值是 10, 5, 1, 0.1 剛好能湊到 16.1，並且也這麼湊巧，四張郵票剛好是最佳解.
如果把郵票的面值改變，新的郵票面值有
$5, $3.7, $3.1, $2.9, $2.3, $2, $1.7, $1.3, $1, $0.5, $0.2, $0.1
當我們再用同樣的程式去執行時，得到的答案會是 $5, $5, $5, $1, $0.1 ，需要 5 張郵票．但你認真排列之後，你會發現有一個更好的答案，那就是 $5, $3.7, $.3.7, $3.7，只需要 4 張郵票即可．此時便可發現貪心方法並無法保證我們一定能夠得到最佳解．如果得到最佳解，只能說題目本身的特性剛好能讓貪心方法得到最佳解而己．
從第一個問題來看，最佳解的答案有幾個特性
1. 答案最多一個 $0.1，因為若有兩個以上的 $0.1，便可以用 $0.2 來替代．
2. 答案最多兩個 $0.2，因為若有三個以上的 $0.2，便可以用一個 $0.5 和一個 $0.1 來替代.
3. 答案不會存在兩個 $0.2 和一個 $0.1，因為可以用一個 $0.5 替代.
還有一些其他的特性可以類推而得．同時，第二個問題可以用同樣的方式來找出最佳解的特性．第二個問題的其中一個特性就是，不該出現兩個 $5, 一個 $1 和一個 $0.1，因為可以用三個 $3.7 來替代，所以我們用貪心方法所得到的答案便不會是最佳解．
