c Balaji Raghavachari 75 Algorithm Design and Analysis DP example Activity selection problem c Balaji Raghavachari Given a set S a1 a2 an of n proposed activities that wish to use a resource such as a lecture hall which can be used by only one activity at a time 76 Algorithm Design and Analysis An input instance to ASP 8 12 0 6 Each activity has a start time si a finish time fi and a profit Pi that is gained if activity ai is actually scheduled to use the resource Activity ai takes place during the half open time interval si fi 6 10 3 5 1 4 3 8 5 9 2 13 Problem Find a set of compatible activities to use the resource that maximizes the profit 0 1 For convenience assume activity a0 that precedes all activities with P0 0 77 Algorithm Design and Analysis Recursive solution using divide and conquer Define ASP i Maximum profit obtained by a schedule selected from the first i activities a1 ai max ASP i 1 Pi ASP j where j is the largest index less than i with fj si Recursive algorithm takes 2n time though there are only n distinct subproblems 4 5 6 7 8 9 10 11 12 13 14 c Balaji Raghavachari 78 Algorithm Design and Analysis Correctness of ASP recurrence 2 Otherwise ai is in Opt It yields a profit of Pi Let j be the largest index with fj si Since they are sorted f1 f2 fj si all activities in a1 aj are compatible with ai Also fi 1 fi 2 fj 1 si so aj 1 ai 1 are incompatible with ai So an optimal solution can use only a subset of a1 aj with ai and by the I H the best solution for this subset is ASP j The total profit in this case is Pi ASP j Recurrence for ASP i ASP i 3 1 If ai is not in Opt then it selects a subset of a1 ai 1 with maximum profit which is ASP i 1 I H Optimal substructure property If aj is in an optimal schedule then profit obtained till time fj is ASP j 0 2 Proof by induction on i Base If i 0 there are no activities and the profit is 0 Step For i 0 consider Opt a set of activities in a1 ai that generates maximum profit Sort the activities by their finish times ASP 0 12 14 8 11 5 7 Activities ai and aj are compatible if the intervals si fi and sj fj do not overlap c Balaji Raghavachari So ASP i max ASP i 1 Pi ASP j c Balaji Raghavachari 79 Algorithm Design and Analysis Dynamic program to solve the activity selection problem c Balaji Raghavachari 80 Algorithm Design and Analysis R T of program below O n2 It can be improved to O n log n by using binary search in the while loop to find j Finding a solution Assume activity 0 in interval 0 0 with 0 profit ASP 0 0 for i 1 to n do j i 1 while fj si do j j 1 if ASP i 1 ASP j Pi then ASP i ASP i 1 U se i N else ASP i ASP j Pi U se i Y P re i j return ASP U se P re c Balaji Raghavachari 81 ASP i Algorithm Design and Analysis Use j Max of Algorithm to print scheduled activities Input arrays ASP U se P re PSA ASP U se P re n if n 0 then while U se n N do n n 1 PSA ASP U se P re P re n Print n c Balaji Raghavachari 83 Algorithm Design and Analysis Alternate solution to ASP i si fi Pi 1 1 4 3 2 3 5 2 3 0 6 6 4 5 7 2 5 3 8 5 Assume activities are sorted by start times or finish times Add dummy actitities a0 and an 1 at times 0 and respectively Let Sij ak sk fi and fk sj be those activities that fit between activities ai and aj Let Cij be the maximum total profit of a set of compatible activities in Sij Our objective is to compute C0 n 1 6 5 9 4 Recurrence for Cij Base case Cij 0 if Sij 7 6 10 4 8 8 11 3 9 8 12 4 10 2 13 11 11 12 14 2 Solution Cij max Pk Cik Ckj ak Sij Explanation If an optimal solution Opt to Sij contains an activity ak then it splits the time interval fi sj into two sub intervals fi sk and fk sj and the optimal solution for these sub intervals are Cik and Ckj respectively Since ak in Opt is not known try all possible ak Sij
View Full Document
Unlocking...