Re: [問題] 數值合併

看板Prob_Solve作者 (KERORO軍曹)時間18年前 (2006/07/10 10:16), 編輯推噓4(4推 0噓 0→)
留言4則, 1人參與, 最新討論串5/15 (看更多)
※ 引述《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
推
07/10 10:24, , 1F
you're right, 這也不是 optimal solution
07/10 10:24, 1F
推
07/10 10:24, , 2F
看來不簡單喔 @@
07/10 10:24, 2F
推
07/10 10:24, , 3F
btw, 你是怎麼知道有 n lg n 的 solution 的呢?
07/10 10:24, 3F
推
07/10 10:32, , 4F
感覺上, 這問題是要造出某種 balacne 的 tree
07/10 10:32, 4F
‣ 更多 windows2k 的文章
文章代碼(AID): #14iRXjHQ (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 5 之 15 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共15篇)
‣ 更多 windows2k 的文章
文章代碼(AID): #14iRXjHQ (Prob_Solve)