This is an old revision of the document!
Table of Contents
Section 6.1: Weighted Interval Scheduling: A Recursive Procedure
Compute-Opt(j)
If j----0 then
Return 0
Else
Return max(v<sub>j</sub> + Compute-Opt(p(j)), Compute-Opt(j - 1))
Endif
M-Compute-Opt(j)
If j = 0 then
Return 0
Else if M[j] is not empty then
Return M[j]
Else
Define M[j] = max(v<sub>j</sub> + Compute-Opt(p(j)), Compute-Opt(j - 1))
Return M[j]
Endif
Find-Solution(j)
If j = 0 then
Output nothing
Else
If v<sub>j</sub> + M[p(j)] ≥ M[j - 1] then
Output j together with the result of Find-Solution(p(j))
Else
Output the result of Find-Solution(j - 1)
Endif
Endif
Section 6.2: Principles of Dynamic Programming: Memoization or Iteration over Subproblems
Iterative-Compute-Opt
M[O] = 0
For j = l, 2 .....n
M[j] = max(v<sub>j</sub> + M[p(j)], M[j - 1])
Endfor
