问答题
试题四(共15分)
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
[说明]
用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。
问答题
[问题1](9分)
根据以上说明和C代码，填充C代码中的空(1]～(5)。
【正确答案】(1) p[x1[y][0]＝1
(2)p[x][y][k]＝p[x-a][k-1][y][k-1]
(3)y—b[k-1]＝0
(4)p[x][y][n]==1 或p[x][y][n] 或 p[x][y][n]!=0
(5)(x＞＝y)?x：y
【答案解析】
问答题
[问题2](2分)
根据以上C代码，算法的时间复杂度为____(6)____(用O符号表示)。
【正确答案】
(6)O(m2n)
【答案解析】
问答题
【正确答案】(7)(1，1，2，2，1，1)
(8) 15
【答案解析】 根据题意和算法，可以得到若作业1、2、5和6在处理机A，而作业3和4在处理机B上处理，可以得到最优解。此时在处理机A上的处理时间为14，而在处理机B上的处理时间为15，因此最优解的值，即最短的处理时间为15，而最优解为(1，1，2，2，l，1)。