Page 530 - Discrete Mathematics and Its Applications

8.1 Applications of Recurrence Relations 509
EXAMPLE 6
Algorithm1,forcomputingthemaximumtotalnumberofattendees.Weensurethatthealgorithm
Talk 7 p(7) = 4
Talk 6 p(6) = 2
Talk 5 p(5) = 0
Talk 4 p(4) = 0
Talk 3 p(3) = 1
Talk 2 p(2) = 0
Talk 1 p(1) = 0
8 a m. 9 a m. 10 a m. 11 a m. 12 noon 1 p m. 2 p m. 3 p m.
FIGURE 5 A Schedule of Lectures with the Values of p(n) Shown.
Consider seven talks with these start times and end times, as illustrated in Figure 5.
Talk 1: start 8 a.m., end 10 a.m. Talk 5: start 8:30 a.m., end 2 p.m.
Talk 2: start 9 a.m., end 11 a.m. Talk 6: start 11 a.m., end 2 p.m.
Talk 3: start 10:30 a.m., end 12 noon Talk 7: start 1 p.m., end 2 p.m.
Talk 4: start 9:30 a.m., end 1 p.m.
Find p(j) for j = 1, 2,..., 7.
Solution: We have p(1) = 0 and p(2) = 0, because no talks end before either of the first two
talks begin. We have p(3) = 1 because talk 3 and talk 1 are compatible, but talk 3 and talk 2
are not compatible; p(4) = 0 because talk 4 is not compatible with any of talks 1, 2, and 3;
p(5) = 0 because talk 5 is not compatible with any of talks 1, 2, 3, and 4; and p(6) = 2 because
talk 6 and talk 2 are compatible, but talk 6 is not compatible with any of talks 3, 4, and 5. Finally,
p(7) = 4, because talk 7 and talk 4 are compatible, but talk 7 is not compatible with either of
talks 5 or 6. ▲
To develop a dynamic programming algorithm for this problem, we first develop a key
recurrence relation. To do this, first note that if j ≤ n, there are two possibilities for an optimal
schedule of the first j talks (recall that we are assuming that the n talks are ordered by increasing
end time): (i) talk j belongs to the optimal schedule or (ii) it does not.
Case (i): We know that talks p(j) + 1,...,j − 1 do not belong to this schedule, for none of
these other talks are compatible with talk j. Furthermore, the other talks in this optimal schedule
must comprise an optimal schedule for talks 1, 2,...,p(j). For if there were a better schedule
for talks 1, 2,...,p(j), by adding talk j, we will have a schedule better than the overall optimal
schedule. Consequently, in case (i),wehave T(j) = w j + T(p(j)).
Case (ii): When talk j does not belong to an optimal schedule, it follows that an optimal
schedule from talks 1, 2,...,j is the same as an optimal schedule from talks 1, 2,...,j − 1.
Consequently, in case (ii),wehave T(j) = T(j − 1). Combining cases (i) and (ii) leads us to
the recurrence relation
T(j) = max(w j + T(p(j)), T(j − 1)).
Now that we have developed this recurrence relation, we can construct an efficient algorithm,
is efficient by storing the value of each T(j) after we compute it. This allows us to compute T(j)