阅读下列说明C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为a
i
和b
i
。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。
算法步骤：
(1)确定候选解上界为最短的单台处理机处理所有作业的完成时间m，
问答题
根据以上说明和C代码，填允C代码中的空(1)～(5)。
【正确答案】正确答案：(1)p[x][y][0]=1(2)p[x][y][k]=p[x—a[k—1\]\][y][k—1](3)y-b[k一11>=0 (4)p[x][y][n]=1，或p[x][y][n]或p[x][y][n]!=0(5)(x>=y)?x：y
【答案解析】解析：从schedule()函数的第一个程序段可以看出，该段程序主要进行初始化第一个作业，下标以0开始，即p[x][y][0]=1，内层循环里的p[x][y][k]=0用于初始化后面的n-1个作业。第二个程序段是对后面的n—1个作业，确定。p(x，y，k)的值。x．a[k．1]>=0的判定条件若成立，则表示第k个作业由机器A处理，完成k一1个作业时机器A花费的时间是x—a[k—1]，即p[x][y][k]=p[x—a[k—1][y][k—1]。(3)空要求填入一判定条件，由其后的执行语句可知，第k个作业由机器B
问答题
根据以上C代码，算法的时间复杂度为(6)(用O符号表示)。
【正确答案】正确答案：(6)O(m
2
n)
【答案解析】解析：从程序的循环层数即可看出算法的时间复杂度。程序的最高循环层数为3层。最外层循环变量的变化范围是1一n一1，次外层循环变量的变化范围是0～m，内层循环变量的变化范围是0~m，所以时间复杂度为O(m
2
n)。
问答题
考虑6个作业的实例，各个作业在两台处理机上的处理时间如表15一1所示。该实例的最优解为(7)，最优解的值(即最短处理时间)为(8)。最优解用(x
1
，x
2
，x
3
，x
4
，x
5
，x
6
)表示，其中若第i个作业在A上处理，则x
i
=1，否则x
i
=2。如(1，1，1，1，2，2)表示作业1，2，3和4在A上处理，作业5和6在B上处理。
【正确答案】正确答案：(7)(1，1，2，2，1，1)(8)15
【答案解析】解析：为了方便考生更好地理解本算法的思想，现做如下分析：当完成k个作业，设机器A花费了x时间，机器B所花费时间的最小值肯定是x的一个函数，设F[k][x]表示机器B所花费时间的最小值，则F[k][x]=Min{F[k—1][x]+b[k]，F[k．1][x—a[k\]\]}。其中F[k—1][x]+b[k]表示第k个作业由机器B来处理(完成k-1个作业时机器A花费的时间仍是x)，F[k—1][x．a[k\]\]表示第k个作业由机器A处理(完成k—1个作业时机器A花费的时间是x-a[k])。那么单个点对较大值max(x，F[k][x])，表示此时(即机器A花费X时间的情况下)所需要的总时间。而机器A花费的时间x是变化的，即x=0，1，2…x(max)，由此构成了点对较大值序列。要求整体时间最短，取这些点对较大值序列中最小的即是。现分析前两个作业的情况：对于第一个作业：下标以0开始。首先，机器A所花费时间的所有可能值范围：0<=x<=a[0]。设x<0时，设F[0][x]=∞，则max(x，∞)=∞。记法意义见下。x=0时，F[0][01=3，则max(0，3)=3，机器A花费0时间，机器B花费3时间，而此时两个机器所需时间为3；x=1时，F[0][1]=3，max(1，3)=3；x=2时，F[0][2]=0，则max(2，0)=2；那么上面的点对序列中，可以看出当x=2时，完成第一个作业两台机器花费最少的时间为2，此时机器A花费2时间，机器B花费0时间。再来看第二个作业。首先，x的取值范围是：0<=X<=(a[0]+a[11)。当x<0时，记F[1][x]=∞。这个记法编程使用，因为数组下标不能小于0。在这里的实际含义是：x是代表完成前两个作业机器A的时间，a[1l是机器A完成第2个作业的时间，若x