作者windows2k (KERORO军曹)
站内Prob_Solve
标题[问题] 数值合并
时间Sat Jul 8 20:48:15 2006
版上强者很多, 所以我又来问问题了
有一系列的数字, 每次挑两个相邻的数字合并
合并的数字按照原来顺序插入序列之中, 合并的代价为 s , s 为两个数字的和
经过一连串的合并之後, 整个序列会只剩下一个值, 而总合并代价为 S
问怎样的合并动作, 总合并代价会是最小
范例一:
3 4 5 (3,4) 合并 代价 7
7 5 (7,5) 合并 代价 12
12 总代价 19
范例二:
5 3 4 5 (5,3) 合并 代价 8
8 4 5 (4,5) 合并 代价 9
8 9 (8,9) 合并 代价 17
17 总代价 34
5 3 4 5 (3,4) 合并 代价 7
5 7 5 (5,7) 合并 代价 12
12 5 (12,5) 合并 代价 17
17 总代价 36
可见greedy algorithm并非最佳解
用Dynamic programming的话, 存在一个 O(n^3)的演算法
不过有一个 O(nlogn)的演算法, 却不得其门而入
有谁可以提示一下, 感激不尽
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.115.220.140
1F：推 ledia:huffman ? 07/08 20:56
2F：推 ericbibo:嗯~huffman's algorithm...每次都挑最小的两个出来合并 07/08 21:02
3F：推 windows2k:顺序不得修改, 看看第二个范例, 3和4合并之後在双5之间 07/08 21:04