多完成一个作业)。带限期作业排序问题就是要在所给的作业集合中 选出总效益值最大的相容子集。 这个问题可以看作是活动安排问题的推广,作业i的起始时间 为0≤s≤f-1.而活动安排问题中的效益值可以认为全是1。因此,很 容易想到贪心准则应该是尽量选取效益值最大的作业安排。但由于起 始时间是一个区间,可以将后面考虑的作业插到前面安排时剩余的空 闲时间片里,这是不同的地方。 带限期作业安排的贪心算法伪代码 Greedy Job(f,p,n)/ln]和p[1n]分别代表各项作业的限期和效益 ∥值,而且n项作业的排序满足:p1≥p2≥…≥p local. J={1}; for i from 2 to n do ifJu{i}中的作业是相容的then J=J∪{i};∥将i加入解中 endif endfor end Greedy Job 定理2算法 GreedyJob对于作业排序问题总是得到最优解。 证明:假设贪心算法所选择的作业的集合J不是最优解,则一定 有相容的作业子集I,其产生更大的效益值。并假定I是具有最大效 益值的相容作业子集中使得Ⅰ⌒J最大者。这两个作业集之间没有包多完成一个作业）。带限期作业排序问题就是要在所给的作业集合中 选出总效益值最大的相容子集。 这个问题可以看作是活动安排问题的推广， 作业 i 的起始时间 为 0≤si≤fi-1. 而活动安排问题中的效益值可以认为全是 1。因此，很 容易想到贪心准则应该是尽量选取效益值最大的作业安排。但由于起 始时间是一个区间，可以将后面考虑的作业插到前面安排时剩余的空 闲时间片里，这是不同的地方。 带限期作业安排的贪心算法伪代码 GreedyJob(f, p, n) //f[1:n]和 p[1:n]分别代表各项作业的限期和效益 //值，而且 n 项作业的排序满足：p1 ≥ p2 ≥ … ≥ pn local J; J={1}; for i from 2 to n do if J ∪ {i} 中的作业是相容的 then J= J ∪ {i}; // 将 i 加入解中 endif endfor end GreedyJob 定理 2 算法 GreedyJob 对于作业排序问题总是得到最优解。 证明：假设贪心算法所选择的作业的集合 J 不是最优解，则一定 有相容的作业子集 I，其产生更大的效益值。并假定 I 是具有最大效 益值的相容作业子集中使得 I ∩ J 最大者。这两个作业集之间没有包