对于本题的作业处理问题,用图4－1的贪心算法策略,能否求得最高收益?(6)。用贪心算法求解任意给定问

Question

对于本题的作业处理问题，用图4-1的贪心算法策略，能否求得最高收益?(6)。用贪心算法求解任意给定问题时，是否一定能得到最优解?(7)。

Answer 1

正确答案：(6)能或可以、行及其他含义相同的词语 (7)不能或不可以、不行及其他含义相同的词语
(6)能，或可以、行及其他含义相同的词语 (7)不能，或不可以、不行及其他含义相同的词语 解析：本题考查的是算法的设计和分析技术。
问题1考查的是贪心算法的流程图。第(1)空表示第2个作业到第n个作业的主循环，i是循环控制变量，故第(1)空填入i<=n。
应注意到数组／中的作业J[i](1≤i≤k)是在其期限之前完成的作业，且d[J[i]]≤d[J[i+1]] (1≤id[i]。另一方面， J[D[R]]与r的关系只有两种：J[d[r]]>r，表示还可能在J[1]与J[r]之间插入作业i；J[d[r]]=r，表示不可能在J[1]～J[r]之间插入作业i。J[d[r]]问题2是本题算法的一个实例。6个作业的收益已经按降序排好序。根据流程图，将作业1，2，4和5放入数组J中，并得到总收益为220，具体过程如表4-1所示。

问题3考查算法策略。对于该题，贪心策略可以求得最优解。但不是所有的问题都能通过贪心策略来求得最优解，一个典型的例子是0-1背包问题。举例如下，有三件物品，背包可容纳50磅重的东西，每件物品的详细信息如表4-2所示，问如何装包使得其价值最大?

如果按贪心策略求解该问题，优先选择单位价值最大的物品，则先选择物品1，然后选择物品2。由于此时背包容量还剩下50-10-20=20，不足以容纳物品3，故总价值为 60+100=160美元。但若选择物品2和物品3，容量总和为20+30，小于等于总容量50，得到总价值为100+120=220，会得到更优解。此时用贪心策略不能得到最优解。