现在的位置: 首页 > 综合 > 正文

陨石比较实验问题

2017年12月23日 ⁄ 综合 ⁄ 共 438字 ⁄ 字号 评论关闭

现从A星和B星分别取来n1,n2块陨石碎片,需要做n=min(n1,n2)次实验,每次从两堆陨石各取一颗来比较,每颗陨石只能参与比较一次。每个陨石有一个重量,记为w1[i] 和 w2[i],现在我们希望选取一种比较方案,使得每次比较的两个陨石重量之差的绝对值的总和最小。

 

第一反应当然是分别两堆陨石排序。

然后用动态规划来做,其实跟字符串相似距离蛮像的,只是权的计算不一样而已。

记  s [i ,j ] 表示A星前  i 个陨石和B星前 j 个陨石比较产生的总和。

则: S [i, j] =  :

                              1.  if  i > j  , S[i,j] = min {  S[i -1 , j] , S [i-1 ,j-1 ]+ | w1[i] - w2[j] | } ;

                              2. if   i == j ,   S[i ,j ] = S[i-1,j-1] + | w1[i] - w2[j]  | ;

                              3. if  i< j , 与1类似;

 

抱歉!评论已关闭.