Activity Scheduling w Revenue Algorithms Dynamic Programmin

Activity Scheduling w/ Revenue - Algorithms (Dynamic Programming)

LINK to CLRS: http://io.acad.athabascau.ca/~oscar/ebook/algorithms.pdf

Section 16.1 can found at page 436 on the pdf.

In the greedy algorithm class you found out that one can\'t use a greedy algorithm when the problem is to maximize the revenue from activities, and we noted that dynamic programming will apply. Here you will develop the DP solution, but you are responsible for the details. Your analysis in (a) and (b) below should mirror that of section 16.1 of Introduction to Algorithms (CLRS). Describe the structure of an optimal solution A_ij for S_ij, as defined in CLRS, and use a cut and paste argument to show that the problem has optimal substructure. Write a recursive definition of the value val[i,j] of the optimal solution for S_ij. val[i, j] = Translate that definition into pseudo code that computes the optimal solution.

Solution

Optimal Substructure Analysis:-
A dynamic programming begins with the choices that we are going to make to make out solution optimal. Here we choose the steps assuming that the final solution that we are going to get will be the optimal solution.
Now according to the question, let us define the Aij to be the optimal solution at the end of the problem.

At some point of time we need to include the activity called ak which has starting time sk and the finish time fk.
The optimal solution to these sub problems would be:-
A_ik = Aij(intersection) S_ik \" The optimal solution to S_ik
A_kj = Aij (intersection) S_kj \" THe optimal solution to S_kj.

Hence the structure for the optimal solution of the problem would be
A_ij = A_ik (union) {ak} (union) A_kj , where ak is some task that has been chosen to make the solution optimal.

By Cust and paste argument an optimal solution for Aij must include the optimal solution for both Aik and Akj, because if sub solution Aik were used then would increase the number of the activities which is actually the contradiction to optimal solution.
There the activity scheduling probelm has optimal structure.

b) Recursive definition for the val[i,j] to get the optimal solution Sij would be
val[i, j] = val[i, k] + val[k, j] + 1 (the 1 is to count one extra step that we included).