Greedy vs. Dynamic programming
 ----------------- ------------@CopyLeft by tsaiwn@csie.nctu.edu.tw
  * Greedy Algorithm (貪心演算法)
      -- At any stage, choose the "locally optimal" solution
         可以找到 feasiable solution
      -- Greedy 方法不一定能找到 optimal solution
         此時須用 Dynamic Programming 方法
      -- examples:
             Coin Change problem  (如下)
 有興趣可以再看:
             Dijkstra's Shortest Path Algorithm
             Kruskal's Mimimum Cost Spanning Tree Algorithm

*Coin Change problem
 ------------------
    Suppose that we have the following coins:
 1 cent (penny), 5 cent (nickle), 10 cent (dime), 25 cent (quarter)


 如何把要找的錢用最少的 coins 組成? ==> 此時用 Greedy 就可找出最佳解

  For example, 63 cents 最少要幾個 coins?
  Greedy method 就是先選目前看起來最好的 (locally optimal)
    --> 要最少 coin, 當然先選值大的 --> 25 cent * 2 = 50 cents
        63 - 50 = 13  -->  選可用的最大 10 cent
        13 -10 = 3  -->  只好選 3 個 1 cent 的
       ===> 共有 2 個 25cent, 1 個 10cent, 3 個 1 cent  ==> 6 個
       ===> 在此例中這就是最佳解 : 25 + 25 + 10 + 1 + 1 + 1


  ==== ===>但, 有時候 Greedy 方法不一定能找到 optimal solution!
         例: 如果有 21 cent 的 coin
   ?? What if we have coin of 50 cents, 21 cents, 10, 5, 1 cent ?
        則顯然最佳解應該是 3 個 21 cent coin 就共 63 cents
        Greedy ==>    50 + 10 + 1 + 1 + 1      ==> 5 個 ! Wrong !
        Correct answer   ==> 21 + 21 + 21 = 63 cents   ==> 3 個
      此時要用 Dynamic Programming 技巧才能找到最佳解 !

*Dynamic programming (動態程式規劃) 的主要精神是:
   * Divide and conquer 
   * recursive
   * 用 table 或是 array 記住以前算過的答案以節省 recursive 次數 (最重要)

   以這個 找零錢 為例子:
     要找出 63 cents 最少要多少 銅板 ==>
       -->   找 best(1 + 62, 2+61, 3+60, 4+59, 5+58, ..., 31+32)
           ...

     因為會用 array 把 1, 2, 3, 4, 5, 6, 7, 8 cent, ... 的最佳解記住
     所以 recursive 不會很深 :-)

*** ==========================================================

Dijkstra's Shortest Path Algorithm

                              (1)
                         10 /   |  \   100
                           /  30|    \
                         (2)    |    (5)
                          |      \_/  |
                          |     _/\   |
                          |    /   \  |
                            /--    v  |
                         (3)<-------(4)

Kruskal's Mimimum Cost Spanning Tree Algorithm
=============================================================