Proof of the theorem Why theorem 16.1 is valuable? The second part of the theorem is trivial Reduce the subproblems To prove the first part, let A, is an optim We can compute the optimal solution in a solution of Sj, and order the activities in A j top-down fashion, rather than the bottom in monotonically increasing order of finish up manner used in dynamic programming time. Let ax be the first activity in Aj, if ak=am, then we have done, else we can replace a with am in Aj, and it changes to another solution! It is optimal too The solution constructing 课堂练习 procedure Find the activity ax which has the earliest 实例:S={(09),(1,2),(1,3),(2,5),(49) finish time in So.n+1, and it left a problem (58),(7,9),(8,12),(7,11),(9,11),(11,12)} Sk.n+, then one of the optimal solution is 写出递归算法,并模拟算法的实现 faJU An+. Where An+1 is the optimal solution of S 写出叠代(递推)算法,并模拟实现。 Find the activity as which has the earliest finish time in A,n+1… Problems on Greedy Elements of the greedy strategy Algorithm Not all greedy algorithm generate the 1. Determine the optimal substructure of the optimal solution if we choose the least duration activity as our activity selection 2. Develop a recursive solution strategy in the activity-selection problem 3. Prove that at any stage of the recursion, one of the optimal choices is the greedy choice. Thus then it does not always create the optimal it is always safe to make the greedy choice solution Show that all but one of the subproblems nother greedy algorithm for induced by having made the greedy choice are ction problem? empty 6. Convert it to an iterative one4 Proof of the theorem •The second part of the theorem is trivial. •To prove the first part, let Aij is an optimal solution of Sij, and order the activities in Aij in monotonically increasing order of finish time. Let ak be the first activity in Aij, if ak=am, then we have done, else we can replace ak with am in Aij, and it changes to another solution! It is optimal too! Why theorem 16.1 is valuable? •Reduce the subproblems •We can compute the optimal solution in a top-down fashion, rather than the bottom￾up manner used in dynamic programming. 清华大学 软件学院 宋斌恒 21 The solution constructing procedure •Find the activity ak which has the earliest finish time in S0,n+1, and it left a problem Sk,n+1, then one of the optimal solution is {ak }U Ak,n+1. Where Ak,n+1 is the optimal solution of Sk,n+1 •Find the activity as which has the earliest finish time in Ak, n+1… … 清华大学 软件学院 宋斌恒 22 课堂练习 •实例：S={(0,9), (1,2), (1,3), (2,5), (4,9), (5,8), (7,9), (8,12), (7,11), (9,11), (11,12)} •写出递归算法，并模拟算法的实现， •写出叠代（递推）算法，并模拟实现。 Problems on Greedy Algorithm •Not all greedy algorithm generate the optimal solution: if we choose the least duration activity as our activity selection strategy in the activity-selection problem, then it does not always create the optimal solution •Can you find another greedy algorithm for the activity-selection problem? Elements of the greedy strategy 1. Determine the optimal substructure of the problem 2. Develop a recursive solution 3. Prove that at any stage of the recursion, one of the optimal choices is the greedy choice. Thus, it is always safe to make the greedy choice 4. Show that all but one of the subproblems induced by having made the greedy choice are empty 5. Develop a recursive algorithm 6. Convert it to an iterative one