c Balaji Raghavachari 75 Algorithm Design and Analysis✬✫✩✪DP example: Activity selection problem• Given a set S = {a1, a2, ..., an} of n proposed activitiesthat wish to use a resource, such as a lecture hall,which can be used by only one activity at a time.• Each activity has a start t ime si, a finish time fi, and aprofit Pithat is gained if activity aiis actuallyscheduled t o use the resource. Activity aitakes placeduring the half-open time interval [ si, fi).• Activities aiand ajare compatible if the inte r vals [si, fi)and [sj, fj) do not overlap.• Problem: Find a set of compatible activities to use theresource tha t maximizes the profit.• For convenience, assume activ ity a0that precedes allactivities wi th P0= 0.c Balaji Raghavachari 76 Algorithm Design and Analysis✬✫✩✪An input instance to ASP141312111098765432100-68-126-103-51-45-78-1112-143-85-92-13c Balaji Raghavachari 77 Algorithm Design and Analysis✬✫✩✪Recursive solution using divide-and-conquer• Sort the activities by their finish t i mes.• Define ASP (i) = Maximum profit obtained by aschedule select ed from the first i activitie s {a1, . . . , ai}.• Optimal substructure property: If ajis in an optimalschedule, then profit obtained till time fjis ASP (j).• Recurrence for ASP (i) :ASP (0) = 0ASP (i) = 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 areonly n distinct subproblems.c Balaji Raghavachari 78 Algorithm Design and Analysis✬✫✩✪Correctness of ASP recurrenceProof by induction on i. Base: If i = 0, there are noactivities, and the profit is 0. Step: For i > 0, consider Opt,a set of activities in a1..aithat generat es maximum profit.1. If aiis not in Opt, then it selects a subset of a1..ai−1with maximum profit, which is ASP (i − 1) (I.H.)2. Otherwise, aiis in Opt. It yields a profit of Pi. Let j bethe largest index with fj≤ si. Since they are sorted,f1≤ f2≤ . . . ≤ fj≤ si, all activi ties in a1, . . . , ajarecompatible with ai. Also, fi−1≥ fi−2≥ . . . ≥ fj+1> si, soaj+1, . . . , ai−1are incompatible with ai. So an optimalsolution can use only a subset of {a1, . . . , aj} with ai,and by the I.H., the best solution for this subset isASP (j). The total profit i n this case is Pi+ ASP (j).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 problemR.T. of program below = O(n2). It can be improved toO(n l og n) by using binary search in the while loop to find j.// Assume activity 0 in interval [0,0] with 0 profitASP [0] ← 0for i ← 1 to n doj ← i − 1while fj> sidoj ← j − 1if ASP [i − 1] ≥ ASP [j] + PithenASP [i] ← ASP [i − 1]; Use[i] ← ’N’elseASP [i] ← ASP [j] + Pi; Use[i] ← ’Y’; P re[i] ← jreturn ASP, Use, P rec Balaji Raghavachari 80 Algorithm Design and Analysis✬✫✩✪Finding a solution// Algorithm to print scheduled activities// Input: arrays ASP [], U se[], P re[]PSA(ASP, U se, P re, n)if n > 0 thenwhile U se[n] = ’N’ don ← n − 1PSA(ASP, U se, P re, P re[n])Print nc Balaji Raghavachari 81 Algorithm Design and Analysis✬✫✩✪i sifiPiASP (i) Use j Max of1 1 4 32 3 5 23 0 6 64 5 7 25 3 8 56 5 9 47 6 10 48 8 11 39 8 12 410 2 13 1111 12 14 2Solution:c Balaji Raghavachari 83 Algorithm Design and Analysis✬✫✩✪Alternate solution to ASPAssume act i v ities are sorted by start times or finish times.Add dummy actititi e s a0and an+1at times 0 and ∞respectively. Let Sij= {ak|sk≥ fiand fk≤ sj} be thoseactivities t ha t fit between activities aiand aj. Let Cijbethe maximum total profit of a set of compa tible activities inSij. Our objective is to compute C0,n+1.Recurrence for Cij(Base case: Cij= 0 if Sij= ∅):Cij= maxak∈Sij{Pk+ Cik+ Ckj}.Explanation: If an optimal solution (Opt) to Sijcontainsan activi ty ak, then it splits the time interval [fi, sj) into twosub-intervals [fi, sk) and [fk, sj), and the optimal solution forthese sub-intervals are Cikand Ckjrespectively. Since akinOpt is not known, t r y all possible ak∈
View Full Document
Unlocking...