作者windows2k (KERORO军曹)
站内Prob_Solve
标题Re: [问题] 数值合并
时间Sun Jul 9 17:44:53 2006
※ 引述《march20 ()》之铭言：
: 推 ericbibo:嗯~huffman's algorithm...每次都挑最小的两个出来合并 07/08 21:02
: : 不过有一个 O(nlogn)的演算法, 却不得其门而入
: 看到 n log n , 大胆猜看看.
: 我猜最佳合并法就是 s_x,...,s_m 和 s_(m+1),...,s_y 先各自合并, 接着再并起来.
假设有这样一个数列
10 7 2 4 12 6
用 huffman algorithm
10 7 6 12 6 cost : 6
10 7 12 12 cost : 12
12 12 17 cost : 17
24 17 cost : 24
41 cost : 41
Total Cost: 100
用版大的方法:
Total Sum: 41
所以我们要将
(10 7 2) (4 12 6)分别进行合并
(10 7 2) Total Cost: 28
(4 12 6) Total Cost: 38
19 22 Cost : 41
Total Cost: 107
Optimal Solution:
10 7 2 4 12 6
10 7 6 12 6 cost : 6
10 7 6 18 cost : 18
10 13 18 cost : 13
23 18 cost : 23
41 cost : 41
Total Cost: 101
--
在没有"限制"顺序的情况下, Huffman Algorithm可以找到最佳解
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.115.220.140