演算法 Algorithm ─ Greedy Algorithm PART 4

霍夫曼編碼Huffman

編碼方式：
             ○ 依出現頻率低的兩碼先編排，再和頻率次低者編排
               ○ 若有頻率相近者可先編排再與已經編排好的二元樹進行合併
                  

範例：   字元    出現頻率
               a           7
               b           5
               c          12
               d          17
               e          10
               f            3



解法步驟：

============================================================

0-1 背包問題   &  fractional 背包問題
 
    ※ 貪婪演算法的一種
    ※ 如何在一定的空間內裝下最有價值的物品，並且不浪費空間！


 範例：某一超市舉辦活動，店家給予一只負重100g的袋子並提供餅乾、巧克力、糖果讓參加者隨意裝袋，但限制重量不能超過100g ，請問該如何分配裝袋的數量且裝回最划算的商品呢?


餅乾    25g(1包) = $ 375
巧克力 40g(1包) = $ 800
糖果    60g(1包) = $ 600


0-1 背包問題

解法：
         ○ 以一個單位取值
         ○ 不能將一個單位再拆開為更小單位，要的話就拿，不要就都不能拿

此例題如果以 0-1 背包問題法來解 無法求得最佳解
  
 ------------------------------------------------------------------------------------------------------------------------------------

fractional 背包問題

解法：
         ○ 可以將一個單位再拆開為更小單位，需要的話就拿多少

 此例題如果以 factional 背包問題法來解 可求得比最佳解更棒的結果