Re: [問題] 數值合併
※ 引述《march20 ()》之銘言：
: 推 ericbibo:嗯~huffman's algorithm...每次都挑最小的兩個出來合併 07/08 21:02
: : 不過有一個 O(nlogn)的演算法, 卻不得其門而入
: 看到 n log n , 大膽猜看看.
: 我猜最佳合併法就是 s_x,...,s_m 和 s_(m+1),...,s_y 先各自合併, 接著再併起來.
假設有這樣一個數列
10 7 2 4 12 6
用 huffman algorithm
10 7 6 12 6 cost : 6
10 7 12 12 cost : 12
12 12 17 cost : 17
24 17 cost : 24
41 cost : 41
Total Cost: 100
用版大的方法:
Total Sum: 41
所以我們要將
(10 7 2) (4 12 6)分別進行合併
(10 7 2) Total Cost: 28
(4 12 6) Total Cost: 38
19 22 Cost : 41
Total Cost: 107
Optimal Solution:
10 7 2 4 12 6
10 7 6 12 6 cost : 6
10 7 6 18 cost : 18
10 13 18 cost : 13
23 18 cost : 23
41 cost : 41
Total Cost: 101
--
在沒有"限制"順序的情況下, Huffman Algorithm可以找到最佳解
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.220.140
討論串 (同標題文章)