问答题
阅读下列说明和C代码，回答下列问题。
[说明]
用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。算法步骤如下。
(1)确定候选解上界为R短的单台处理机处理所有作业的完成时间m，
[说明]
用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。算法步骤如下。
(1)确定候选解上界为R短的单台处理机处理所有作业的完成时间m，
问答题
[问题1]
根据以上说明和C代码，填充C代码中的空缺处。
根据以上说明和C代码，填充C代码中的空缺处。
【正确答案】p[x][y][0]=1
p[x][y][k]=p[x-a[k-1]][y][k-1]
y-b[k-1]＞=0
p[x][y][n]=1或p[x][y][n]!=0或p[x][y][n]或其他等价表示形式
(x＞=y)?x:y
p[x][y][k]=p[x-a[k-1]][y][k-1]
y-b[k-1]＞=0
p[x][y][n]=1或p[x][y][n]!=0或p[x][y][n]或其他等价表示形式
(x＞=y)?x:y
【答案解析】
问答题
[问题2]
根据以上C代码，算法的时间复杂度为______(用O符号表示)。
根据以上C代码，算法的时间复杂度为______(用O符号表示)。
【正确答案】O(m2n)
【答案解析】结合问题1的分析结果，根据题干所给出的C代码，函数schedule有两处三重for循环，时间复杂度为O(m2n)。函数write有一处两重for循环，时间复杂度为O(m2)。因此整个算法的时间复杂度为O(m2n+m2)。由于m2在数量级上小于m2n，因此整个算法的时间复杂度可以表示为O(m2n)。
问答题
[问题3]
考虑6个作业的实例，各个作业在两台处理机上的处理时间如表所示。该实例的最优解为______，最优解的值(即最短处理时间)为______。最优解用(x1，x2，x3，x4，x5，x6)表示，其中若第i个作业在A上处理，则xi=1，否则xi=2。如(1，1，1，1，2，2)表示作业1、2、3和4在A上处理，作业5和6在B上处理。
各个作业在两台处理机上的处理时间
考虑6个作业的实例，各个作业在两台处理机上的处理时间如表所示。该实例的最优解为______，最优解的值(即最短处理时间)为______。最优解用(x1，x2，x3，x4，x5，x6)表示，其中若第i个作业在A上处理，则xi=1，否则xi=2。如(1，1，1，1，2，2)表示作业1、2、3和4在A上处理，作业5和6在B上处理。
| 作业1 | 作业2 | 作业3 | 作业4 | 作业5 | 作业6 | |
| 处理机A | 2 | 5 | 7 | 10 | 5 | 2 |
| 处理机B | 3 | 8 | 4 | 11 | 3 | 4 |
【正确答案】(1,1,2,2,1,1)
15
15
【答案解析】依题意和算法，可以得到若作业1、2、5和6在处理机A上处理，而作业3和4在处理机B上处理，可以得到最优解。此时在处理机A上的处理时间为2+5+5+2=14，在处理机B上的处理时间为4+11=15，因此最优解的值，即最短的处理时间为15，最优解为(1,1,2,2,1,1)。