动态规划之作业调度算法题解

时间:2013-12-25 13:14:39
【文件属性】:

文件名称:动态规划之作业调度算法题解

文件大小:13KB

文件格式:DOC

更新时间:2013-12-25 13:14:39

动态规划作业调度

假设有一台机器,以及在此机器上处理的n个作业a1,a2,...an的集合。每隔作业aj有一个处理时间tj,效益pj,以及最后期限dj。机器在一个时刻只能处理一个作业,而且作业aj必须在tj连续时间单位内不间断地运行。如果作业aj在最后期限dj之前完成,则获得效益pj,但如果在最后期限之后才完成,则没有效益。请给出一个动态规划算法,来寻找能获得最大量效益的调度,假设所有的处理时间都是1到n之间的整数。分析你的算法的执行时间。


网友评论

  • 还不错,不过没有递归函数
  • 还好吧 多多少少还是有点启示作用的
  • 内容、解析很详细,差证明
  • 没有写出动态规划的递归函数,最优子结构证明。