作者windows2k (KERORO軍曹)
站內Prob_Solve
標題Re: [問題] 數值合併
時間Mon Jul 10 10:18:24 2006
※ 引述《march20 ()》之銘言：
: 嗯, 看到這個 case, 給了我一個靈感 (先 po 出來看看)
: Huffman 找值最小的兩個來合併,
: 這裡似乎要找相鄰和最小的兩數來合併.
: 比如 10+7, 7+2, 2+4, 4+12, 12+6, 所以先拿 2,4 來合併.
: 然後 update heap 時, 要將影響到的鄰居一併 update
: 比如第一輪找到 2+4 為最小,
: 那就把 2+4 pop 出來, 這時影響到的 node 就是 7+2 和 4+12
: 要將這兩個值變成 7+6 和 6+12 然後調整 heap.
不知道是否我有誤解你的意思
假設這個例子
5 3 4 5
一開始是先拿 3 4 合併
5 7 5
12 5
17
Total cost:36
Optimal Solution:
5 3 4 5
8 4 5
8 9
17
Total cost:34
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.156.192
1F：推 march20:you're right, 這也不是 optimal solution 07/10 10:24
2F：推 march20:看來不簡單喔 @@ 07/10 10:24
3F：推 march20:btw, 你是怎麼知道有 n lg n 的 solution 的呢? 07/10 10:24
4F：推 march20:感覺上, 這問題是要造出某種 balacne 的 tree 07/10 10:32