假设有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)。
假设有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)。
相关考题：
试题四(共15 分)阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。【说明】某机器上需要处理 n 个作业 job1, job2, …, jobn，其中：(1) 每个作业jobi(1≤i≤n)的编号为 i， jobi有一个收益值 p[i]和最后期限值 d[i]；(2) 机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；(3) job1～jobn 的收益值呈非递增顺序排列，即p[1]≥p[2]≥…≥p[n]；(4) 如果作业jobi在其期限之内完成，则获得收益 p[i]；如果在其期限之后完成，则没有收益。为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图 4-1 是基于贪心策略求解该问题的流程图。(1) 整型数组 J[]有 n 个存储单元，变量 k 表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号， 数组 J[1..k]里的作业按其最后期限非递减排序，即d[J[1]]≤ … ≤d[J[k]]。(2) 为了方便于在数组 J 中加入作业，增加一个虚拟作业 job0，并令d[0] = 0， J[0] = 0。(3) 算法大致思想：先将作业 job1 的编号 1 放入 J[1]，然后，依次对每个作业 jobi (2≤i≤n)进行判定，看其能否插入到数组 J 中，若能，则将其编号插入到数组 J 的适当位置，并保证 J 中作业按其最后期限非递减排列，否则不插入。 jobi能插入数组 J 的充要条件是：jobi 和数组 J 中已有作业均能在其期限之内完成。(4) 流程图中的主要变量说明如下：i：循环控制变量，表示作业的编号；k：表示在期限内完成的作业数；r：若jobi能插入数组 J，则其在数组 J 中的位置为 r+1；q：循环控制变量，用于移动数组 J 中的元素。【问题 1】 （9 分）请填充图4-1 中的空缺(1)、(2)和(3)处。【问题 2】(4 分)假设有 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) 。【问题 3】(2 分)对于本题的作业处理问题， 用图 4-1的贪心算法策略， 能否求得最高收益？ (6) 。用贪心算法求解任意给定问题时，是否一定能得到最优解？ (7) 。
某操作系统的当前资源分配状态如下表所示。假设当前系统可用资源R1、R2和R3的数量为（3，3，2），且该系统目前处于安全状态。那么下列哪些是安全序列？A.A.P2P4P1P3P5B.B.P4P5P3P2P1C.C.P4P2P1P5P3D.D.P5P3P2P1P4E.E.P4P5P2P3P1
前趋图是一个有向无环图，记为：→=(P i ，P j )|P i 完成时间先于 P j 开始时间}。假设系统中进程 P=(P 1 ，P2， P3， P 4 ， P 5 ，P 6 ， P 7 ，P 8 }且进程的前趋图如下：那么，该前驱图可记为（）。A.→={(P1,P2),(P1,P3),(P1,P4 ),(P2,P5),（P3,P2）,（P3,P4）,（P3,P6）,（P4,P7）,（P5,P8）,（P5,P6）,（P7,P8）}B.→={(P1,P2),(P1,P3),(P1,P4),(P2,P5),（P3,P2）,（P3,P4）,（P3,P6）,（P4,P7）,（P5,P8）,（P6,P8）,（P7,P8）}C.→={(P1,P2),(P1,P3),(P1,P4),(P2,P5),（P3,P2）,（P3,P4）,（P3,P5）,（P4,P6）,（P4,P7）,（P6,P8）,（P7,P8）}D.→={(P1,P2),(P1,P3),(P1,P4),(P2,P5),（P3,P2）,（P3,P4）,（P3,P5）,（P4,P6）,（P4,P7）,（P7,P8）,（P6,P8）}
前趋图是一个有效无环图,记为→={pi,pj，pi完成时间先于pj开始时间}。假设系统中进P={p1,p2,p3,p4,p5,p6,p7,p8}，且进程的前趋图如下。那么该前驱图可记为（请作答此空）图中（ ）A.→={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P2),(P3,P4),(P3,P6),(P4,P7),(P5,P8)B.→={(P1,P2),(P1,P4),(P2,P3),(P2,P5),(P3,P4),(P3,P6),(P4,P7),(P5,P6),(P6,P8),(p7,p6)}C.→={(P1,P2),(P1,P4),(P2,P5),(P3,P2),(P3,P4),(P3,P6),(P4,P6),(P4,P7),(P6,P8),(p7,p8)}D.→={(P1,P2),(P1,P3),(P2,P4),(P2,P5),(P3,P2),(P3,P4),(P3,P5),(P4,P7),(P6,P8),(p7,p8)}
前趋图是一个有效无环图,记为-={pi,pj，pi完成时间先于pj开始时间}。假设系统中进P={p1,p2,p3,p4,p5,p6,p7,p8}，且进程的前趋图如下。那么该前驱图可记为（请作答此空）图中（ ）A.-={(P1,P2),(P1,P3),(P1,P4)(P2,P5),(P3,P2),(P3,P4),(P3,P6),(P4,P7),(P5,P6)B.-={(P1,P2),(P1,P4),(P2,P3)(P2,P5),(P3,P4),(P3,P6),(P4,P7),(P5,P6),(P6,P8)(p7,p6)}C.-={(P1,P2),(P1,P4),(P2,P5)(P3,P2),(P3,P4),(P3,P6),(P4,P6),(P4,P7),(P6,P8)(p7,p8)}D.-={(P1,P2),(P1,P3),(P2,P4)(P2,P5),(P3,P2),(P3,P4),(P3,P5),(P4,P7),(P6,P8)(p7,p8)}
前趋图(Precedence Graph) 是一个有向无环图，记为：→={（Pi，Pj ）|Pi must complete before Pj may strat}。假设系统中进程P={P1，P2，P3，P4，P5，P6，P7，P8}，且进程的前驱图如下：那么前驱图可记为：( )A. →={(P2,P1),(P3,P1),(P4,P1),(P6,P4),(P7,P5）,（P7,P6）,（P8,P7）}B. →={（P1,P2）,(P1,P3),(P1,P4),(P2,P5),(P5,P7),(P6,P7）,（P7,P8）}C. →={（P1,P2),(P1,P3),(P1,P4),(P2,P5),（P3,P5),(P4,P6),(P5,P7),(P6,P7),(P7,P8)}D. →={(P2, P1), (P3,P1),(P4,P1),(P5,P2),(P5,P2),(P5,P3),(P6,P4),(P7,P5), (P7,P6),(P8,P7)}
前趋图(Precedence Graph) 是一个有向无环图，记为：→={（Pi，Pj ）|Pi must complete before Pj may strat}。假设系统中进程P={P1，P2，P3，P4，P5，P6，P7，P8}，且进程的前驱图如下：那么前驱图可记为：(6)A. →={(P2,P1),(P3,P1),(P4,P1),(P6,P4),(P7,P5),(P7,P6),(P8,P7)}B. →={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P5,P7),(P6,P7),(P7,P8)}C. →={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P5,P7), (P6,P7),(P7,P8)}D. →={(P2,P1),(P3,P1),(P4,P1),(P5,P2),(P5,P2),(P5,P3),(P6,P4), (P7,P5),(P7,P6),(P8,P7)}
上接第2题，如果进程按照（）序列执行，那么系统状态是安全的。A．P1-＞P2-＞P4-＞P5-＞P3B．P5-＞P2-＞P4-＞P3-＞P1C．P4-＞P2-＞P1-＞P5-＞P3D．P5-＞P1-＞P4-＞P2-＞P3