#86 貪心方法是最佳解 ?

最佳解? 這種解答是許多問題所追尋的目標.例如,在一個城市裡找到出發點和目的地的最短距離.直覺來看,若你沒有把所有可能的路徑列出來,你怎麼知道那一個才是最短的.再舉例一個例子,在一個 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 來替代,所以我們用貪心方法所得到的答案便不會是最佳解.


Share:

0 意見:

張貼留言