雁过无痕

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::

《编程之美》读书笔记154.5 磁带文件存放优化

 

对一个已经是最优解的排列,记第i个文件的长度为Bi,被访问概率为Ai。如果交换第i个和第i+1个文件,则平均长度一定不会变小,交换后,访问原第i个文件时,要多访问一个原第i+1文件,长度增加了Ai*Bi+1,而访问原第i+1个文件时,要少访问一个原第i个文件,长度减少了Ai+1*Bi,而访问这两个文件之前和之后的文件,长度没有改变,故有:

Ai*Bi+1 - Ai+1*Bi >=0 Ai/Bi >= Ai+1/Bi+1

由于i可以任意取,因而A0/B0 >= A1/B1 >= A2/B2 >= … >= An-1/Bn-1。也就是说,最优解一定满足P[i]/L[i] 按降序排列,而根据P[i]/L[i]值通过降序排列只能得到唯一确定的排列(只考虑P[i]/L[i]值大小,如果两个文件的P[i]/L[i]值相同,它们位置可以互换而不影响),这个排列必然是最优解。因而,原问题等同于“P[i]/L[i] 降序排列”。

 

 

类似题:

“将一个给定的自然数数组,连接起来得到一个数,求这个数的最大值或最小值”。

posted on 2010-08-16 00:34 flyinghearts 阅读(931) 评论(2)  编辑 收藏 引用 所属分类: 编程之美

评论

# re: 《编程之美》读书笔记15: 4.5 磁带文件存放优化 2012-09-08 15:13 ysttk
拜大神!!  回复  更多评论
  

# re: 《编程之美》读书笔记15: 4.5 磁带文件存放优化 2014-10-15 10:46 zhenzhismile
写的很好,很容易理解,赞  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理