假设有6个作业job1,job2,…,job6; 完成作业的收益数组p=(p[1],p[2],p[3],p[4],p[5],p[6])=(90,80,

Question

假设有6个作业job1，job2，…，job6；

完成作业的收益数组p=(p[1],p[2],p[3],p[4],p[5],p[6])=(90,80,50,30,20,10)；

每个作业的处理期限数组d=(d[1],d[2],d[3],d[4],d[5],d[6])=(1,2,1,3,4,3)。

请应用试题中描述的贪心策略算法，给出在期限之内处理的作业编号序列(4) (按作业处理的顺序给出)，得到的总收益为(5)。

Answer 1

正确答案：这是一道考查贪心算法实例应用的分析题。6个作业job1job2…job6的收益已经按降序排列根据图3-25的算法流程将作业124和5放入数组J中并得到总收益为220具体分析过程见表3-13。
这是一道考查贪心算法实例应用的分析题。6个作业job1，job2，…，job6的收益已经按降序排列，根据图3-25的算法流程，将作业1，2，4和5放入数组J中，并得到总收益为220，具体分析过程见表3-13。