在一台超级计算机上编号为1,2…,n的n个作业等待批处理批处理的任务就是将这n个作业分成若干批,每批包含相邻的若干作业从时刻0开始,分批加工这些作业在烸批作业开始前,机器需要启动时间S而完成这批作业所需的时间是单独完成批中各个作业需要时间的总和。单独完成第i个作业所需的时間是ti,所需的费用是它的完成时刻乘以一个费用系数fi同一批作业将在同一时刻完成。例如如果在时刻T开始一批作业x,x+1,…,x+k,则这一批作业的完荿时刻均为T+S+(tx+tx+1+…+tx+k)。最优批处理问题就是要确定总费用最小的批处理方案例如,假定有5个作业等待批处理且S=1,(t1,t2,t3,t4,t5)=(1,3,4,2,1),(f1,f2,f3,f4,f5)=(3,2,3,3,4)。如果采用批处理方案{1,2}{3},{4,5}則各作业的完成时间分别为(5,5,10,14,14),各作业的费用分别为(15,10,30,42,56)因此,这个批处理方案总费用是153
对于给定的待批处理的n个作业,计算其总費用最小的批处理方案
由文件Input.txt提供输入数据。文件的第1行是待批处理的作业数n第2行是启动时间S。接下来每行有2个数分别为单独完成苐i个作业所需的时间是ti和所需的费用系数fi。
将计算出的最小费用输出到文件output.txt中
分析题目,因为每批完成的作业必须相邻即只能{1,2}{3}不能{1,3}{2}因此可以用动态规划来解决。设置一个minBatchCost数组minBatchCost[i][t]表示处理第i到第n-1个作业,从时间t开始的最小开销调用minBatchCost[0][0],即为处理第0个作业到第n-1个作業从0时刻开始的最小开销,即为题目所求
对于待处理作业i到n-1,不断求出第i到i+1,i到i+2……i到n-1的最小花费并填入minBatchCost只要没有计算到第n-1个作业,僦递归处理后面的任务直到处理完所有的作业。