参考答案:
【问题1】
(1)d[i] = t[i] (2)i=m (3)s[k][count[k]]=i (4)max<d[i]
【问题2】
(5)贪心 (6)O(mn)
【问题3】
(7)0 (8)1、5 (9)2、3、4、6 (10)17
详细解析:
本题考查算法的设计和分析技术中的贪心算法。
贪婪算法(Greedy algorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,它省去了为找最优解要穷尽所有可能而必须耗费的大量时间,它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不要回溯。
【问题1】
根据上述思想和题中的说明,首先将s[][]和d[]数组初始化为0,然后要做的就是按要求“算法基于最长运行时间作业优先的策略,按顺序先把每个任务分配到一台机器上”,可以推断(1)处为d[i] = t[i],此后需将剩下的n-m个任务按顺序分配给空闲的机器,故(2)处将i初始化为以m为起始的任务,即i=m,(3)处所在的位置是分配后n-m个任务,在这个过程中,必须要对s矩阵的内容进行修改,但目前已经出的代码没有这个内容,所以此处必然是对s的修改。从对s矩阵的注释可以了解到,s[i][j]表示机器i运行的任务j的编号,此时涉及任务的机器号为k,而待分配的任务i是机器的第count[k]个任务,即s[k][count[k]]=i,(4)处已经完成了任务的运行,此处需要统计所有机器所运行任务的最长时间,对于每个机器i的运行时间为d[i],存在d[i]大于当前的最大时间Max,就将当前机器的运行时间d[i]赋给Max,即Max<d[i]。
【问题2】
根据以上分析,(5)处采用了贪心算法的策略,而时间复杂度由算法中的两个嵌套for循环和两个非嵌套for循环确定,即为O(mn)。
【问题3】
根据题中算法的思想将任务的前三个任务分给三个机器,再将接下来的任务分给最先空闲的机器,故可知机器0运行任务0,机器1运行任务1、5,机器3运行任务2、3、4、6;且运行的最长时间为17。