直接按照要求模拟,
用到的数据结构无非是队列而以
晕 算法已经在规则1-9中给出来了,按要求写就是了,每小时把挂起的任务和新加入的任务按报酬排序,按顺序加入处理直到没有资源,挂起剩下的任务。
我才晕,这么好算我干吗要问啊?
你要想可以同时进行两项三项甚至n项(只要资源许可)工作的啊,这样才能产生最大的报酬。单纯的排序是没用的.
而且随着任务的增多,更加复杂。
唉,我翻译成中文了还是没理解题意,我解释下例子怎么算的吧。
输入的列子:
10
4 256 3
1 16 2 3 10 5 6
2 128 2 4 30 10 5
2 128 2 4 20 10 5
0
输出的例子:
Case 1: 74
三项工作2时刻同时到达,第二第三项工作2时刻一起进入主机,第一项挂起,在3时刻完成工作后,比预定时间时刻4,快了一小时,那么报酬分别为30+10×(4-3)=40,20+10×(4-3)=30,那么第一项工作在3时刻进入主机,完成工作后是时刻4,晚了一小时,那么报酬为10+(3-4)×6=4,将三项报酬加起来得74。你可以试试其他的算法,比如一项一项完成,得到的报酬都没有74大,所以这是最优解。
所以,没什么规律可言,唯一的办法就是用枚举法,把每种情况都列举出来,算出其报酬,然后再把最大的挑出来。
当然了,三项任务真要写也不难,因为最多有四种情况,要么一项一项做,要么先一项后两项,要么先两项后一项,再就是三项一起(当然啦,资源够不够要判断过)。但是你看看题目,任务最大数是1000项,任务一多,比如有7项,这就意味着有可能先两项后三项再两项。。。也可以先两项后一项再四项,大家想想如果要把所有的情况举遍是否很复杂?
再退一步,如果我知道任务有几项,那还是写的出来的,繁是繁了点,但是有几项任务是用户输入的啊,是不知道的,要写在一个程序里面是否就非常困难。
当然,我迄今想到可以减少计算的办法是先判断资源最大能够进行几项任务,再枚举,但是依然是老问题,得出的结果依然是不知道的,那么问题就跟上面一样了,怎么算才能涵盖所有呢?
这就是问题关键了,说通俗点就是不知道怎么循环,更加不知道怎么控制循环结束,也就是我要问的地方。
[此贴子已经被作者于2006-7-13 21:36:14编辑过]