作者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