问答题 阅读下列算法说明和流程图，根据回答下列问题。
[说明]
某机器上需要处理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]；如果在其期限之后完成，则没有收益。
为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图8-22是基于贪心策略求解该问题的流程图。
问答题 [问题1]
请将图8-22中的空缺处的内容填写完整。
【正确答案】i＜=n
d[J[r]]＞d[i]
J[r+1]=i，或J[q+1]=i
【答案解析】
问答题 [问题2]
假设有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)。
请应用试题中描述的贪心策略算法，给出在期限之内处理的作业编号序列______(按作业处理的顺序给出)，得到的总收益为______。
【正确答案】1,2,4,5或job1、job2、job4、job5及其等价描述形式
220
【答案解析】这是一道考查贪心算法实例应用的分析题。6个作业、job1、job2、...、job6的收益已经按降序排列，根据图8-22的算法流程，将作业1、2、4和5放入数组J中，并得到总收益为220，具体分析过程见表8-9。
表8-9 贪心算法实例执行过程
J数组 收益 考虑的作业 期限 操作
Φ 0 job1 1 放入J中
1 90 job2 2 放入J中
1,2 170 job3 1 不放入J中
1,2 170 job4 3 放入J中
1,2,4 200 job5 4 放入J中
1,2,4,5 220 job6 3 不放入J中
1,2,4,5 220
问答题 [问题3]
对于本试题的作业处理问题，用图8-22的贪心算法能否求得最高收益?______(能或不能)。用贪心算法求解任意给定问题时，是否一定能得到最优解?______(能或不能)。
【正确答案】能，或可以、行及其他含义相同的词语
不能，或不可以、不行及其他含义相同的词语
【答案解析】这是一道判断贪心算法是否能求得最优解的应用分析题。对于本试题的作业处理问题，用图8-22的贪心算法策略，能求得最优解(即能求得最高收益)。但不是所有的问题都能通过贪心策略来求得最优解，一个典型的例子是0-1背包问题。例如，有3件物品，背包可容纳50磅重的东西，每件物品的详细信息如表8-10所示，问如何装包使得其价值最大?
表8-10　贪心算法实例执行过程
物品编号 重量(磅) 价值(美元) 单位价值
R 10 60 6
S 20 100 5
T 30 120 4
如果按贪心策略求解该问题，优先选择单位价值最大的物品，则先选择物品R，然后选择物品S。由于此时背包容量还剩下50-10-20=20，不足以容纳物品T，故总价值为60+100=160美元。但若选择物品S和物品T，容量总和为20+30，小于等于总容量50，得到总价值为100+120=220美元，会得到更优解。此时用贪心策略不能得到最优解。