Re: [問題] 數值合併
看板Prob_Solve (計算數學 Problem Solving)作者windows2k (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
07/10 10:24, 1F
推
07/10 10:24, , 2F
07/10 10:24, 2F
推
07/10 10:24, , 3F
07/10 10:24, 3F
推
07/10 10:32, , 4F
07/10 10:32, 4F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
