Assumption Properties Assumption: the activities are sorted by its S=o whenever ij finish time If we sorted the activities in monotonically ·f6≤f1≤f2≤…≤f<fn+1 creasing order of finish time then the ib problem space is a subset of the Si] for all ·我们能否做到?假设合理否?当然可以, 0≤j≤n+1 我们能够通过排序来完成 Suppose A is an optimal solution of problem Si and ak is in ai then the solutions Ak to Sk and Ay to Sw used within this optimal solution to Si must be optimal as well 最优解的一部分是相关子问题的最 optimal solution can be 优解 constructed by optimal solutions of subproblems 问题的进一步明确:设S是子问题,A是其 最优解,A是A中的一个元素,S和S是 If ak is contains in an optimal solution of Si 相应的子问题,A和A是A按照A前发生 than any optimal solution Ayj which 和A后发生划分的集合,问:A不和A是相 contains a can be expressed by 应的子问题的解吗?是他的最优解吗? Aj=Ak U(akUA "cut-and- paste method Where Ak and Ai are optimal solutions for If a solution Aik to Sik contians more element SK and Ski than Ak we could cut out Ak from A; and paste in Aik, thus producing an anothe onverting a dynamIc A recursive solution programming solution to a greedy solution Let c[ i, j] be the number of the activities in ar Theorem 16 optimal solution to sij, we have c[i,J=0 henever s=Φ; Consider any nonempty subproblem Sy, and let am be the activity in S, with the earliest finish time: Fm= min(fk: ak in S fS=φ c[i,]= Activity am is used in some maximum-size subset max]+4k+l}fS≠ of mutually compatible activities of Sy3 清华大学 软件学院 宋斌恒 13 Assumption • Assumption: the activities are sorted by its finish time: • f0≤f1≤f2≤… ≤fn<fn+1 • 我们能否做到？假设合理否？当然可以， 我们能够通过排序来完成 清华大学 软件学院 宋斌恒 14 Properties • Sij=0 whenever i≥j • If we sorted the activities in monotonically increasing order of finish time, then the subproblem space is a subset of the {Sij} for all 0≤i<j≤n+1. • Suppose Aij is an optimal solution of problem Sij, and ak is in Aij, then the solutions Ai k to Si k and Akj to Skj used within this optimal solution to Sij must be optimal as well. • Notice! The definition of Ai k in the above statment 清华大学 软件学院 宋斌恒 15 最优解的一部分是相关子问题的最 优解 •问题的进一步明确：设Sij是子问题，Aij是其 最优解，Ak是Aij中的一个元素，Sik和Skj是 相应的子问题，Aik和Akj是Aij按照Ak前发生 和Ak后发生划分的集合，问： Aik和Akj是相 应的子问题的解吗？是他的最优解吗？ •“cut-and-paste”method: –If a solution A’ ik to Si k contians more elements than Ai k, we could cut out Ai k from Aij and paste in A’ ik, thus producing an another solution to Sij which has more activities than Aij, which produces a contradiction! 清华大学 软件学院 宋斌恒 16 Optimal solution can be constructed by optimal solutions of subproblems •If ak is contains in an optimal solution of Sij than any optimal solution Aij which contains ak can be expressed by •Aij = Aik U {ak } U Akj •Where Aik and Akj are optimal solutions for Sik and Skj A recursive solution • Let c[ i, j] be the number of the activities in an optimal solution to Sij, we have c[ i, j] = 0 whenever Sij = Φ; ïî ï í ì + + ¹ = = < < f f ij i k j ij c i k c k j S S c i j max{ [ , ] [ , ] 1} if 0 if [ , ] Converting a dynamic￾programming solution to a greedy solution •Theorem 16.1 –Consider any nonempty subproblem Sij, and let am be the activity in Sij with the earliest finish time: Fm = min{fk : ak in Sij} –Then •Activity a m is used in some maximum-size subset of mutually compatible activities of Sij •The subproblem Sim is empty