求助一个组包算法

dongpy

求最佳组包算法。

设数对（X，M），表示访问起始地址为X，字长为M的数据，求解(x1,m1),(x2,m2),...,(xn,mn)的最佳访问组合（即访问的总时间最少）。

前提：
1.每次能访问的最大字长是16，且访问耗时与字长有关，访问字长为1～4、5～8、9～16分别需2、3、4个时间单位。

例如：(0,1),   (1,2),   (5,6),   (10,   2),   (13,   ,   (16,   9)可选组合有：
            (0,3),   (5,16),   (16,9)   =   9个时间单位
            (0,12),(13,12)       =8个时间单位
              ............................
2.组包过程中不能拆包。
例如：(1,10),   (11,10)不能组合为(1,16),(17,4)，因为这样(11,10)被拆成了两部分。

请大家帮忙提供些思路，谢谢！

cugb_cat

先把表情符去掉撒

dongpy

呵呵，部分重发一下：

前提：
1.每次能访问的最大字长是16，且访问耗时与字长有关，访问字长为1～4、5～8、9～16分别需2、3、4个时间单位。

例如：(0,1),   (1,2),   (5,6),   (10,   2),   (13,  8  ） ,   (16,   9)可选组合有：
            (0,3),   (5,16),   (16,9)   =   9个时间单位
            (0,12),(13,12)       =8个时间单位
              ............................
2.组包过程中不能拆包。
例如：(1,10),   (11,10)不能组合为(1,16),(17,4)，因为这样(11,10)被拆成了两部分。

dongpy

具体地说，比如，我们要从外设读取一组数据，假设为(5,6), (10,2), (13,这么3块数据，如果按原始包读取，则需3次，需3+1+3个单位时间，如果组包，只需读取一次(5,16)，4个单位时间。

问题就是求解最佳组包方法。

cugb_cat

把问题转化一下：
就是让字长尽量长，但不能超过16，然后将二元组转化为如下形式：

1. 
   
2. (0,1)(1,3)(5,11)(10,13)(13,21)(16,25)
   

复制代码

相当于坐标系中的点。
且目标不变。
不知道这样理解对不对？
有一个地方不明白：
貌似出不来这个组合吧？
(0,12),(13,12)       =8个时间单位

[ 本帖最后由 cugb_cat 于 2008-2-1 17:05 编辑 ]

galaxywar

这个问题跟矩阵连乘相似, 可以用动态归划.
建一张n*n表,算出所有元素从自已开始读取k(k=1...n)个包的最短时间,(实际这张表应该只有对角线分成的半个). 从1算到n的过程中, 每步都可以直接利用前一步的结果.