作者drkkimo ()
看板Prob_Solve
標題Re: [問題] 數值合併
時間Wed Jul 12 08:36:34 2006
5 3 4 5
中間先合併的話
5 (3+4=7) 5 ->7
(5+7=12) 5 ->12
(12+5=17) ->17
TC=7+12+17=36
另一種方法的話
(5+3=8) 4 5->8
8 (4+5=9)->9
(8+9=17)->17
TC=8+9+17=34
所以不斷找二二合併代價最小的貪婪法 並不一定能找到最佳解
這點前面的討論也早就討論過了 如果沒順序分別的問題才可以每次找最小的二個數字
出來合併 像霍夫曼編碼那樣
: 17 總代價 36
: 其實有個演算法大家可以試看看..不一定最快但是可以找出optimal sol
: 以5 3 4 5來說 先對兩個node 算出cost 會得到
: 8 4 5 cost:8
: 5 7 5 cost:7
: 5 3 9 cost:9
: 然後再對那些cost裡面抓最小cost繼續做
: 所以現在seq 變成: 5 7 5 cost:7
: repeat:
: 12 5 cost: 7 + 12
: 5 12 cost: 7 + 12
: etc...
: 這樣的話complexity time:
: repeat n times:
: 對每兩個node做compute(n) +
: 所有node丟到heap 並建出min heap(nlogn)
: 從min heap pop min cost(1)
: total : n*nlogn
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.172.205.84