This is an old revision of the document!
−Table of Contents
This chapter introduces a new design technique. Instead of using greedy algorithms or divide and conquer, we use dynamic programming. It comes from the divide and conquer method but is the opposite of greedy solutions. This techniques divides a problem into subproblems then builds up solutions to those subproblems until it reaches the full problem. It is close to brute-force.
Chapter 6.1
Weighted Interval Scheduling: A Recursive Procedure
In this section we see our first example of dynamic programming applied to the interval scheduling we previously solved. There are two stages to our process: first the recursive procedure then an iterative algorithm. This problem is different from our previous greedy approach because each interval has a certain weight/value associated with it. Our problem is to schedule as many nonoverlapping intervals as possible and maximize the value of the schedule.
The problem has n intervals 1,…n. Each request i has a start time si,finish time fi, and a value vi. We want to maximize the total value of a set of all mutually compatible intervals.
The Recursive Algorithm
Our previous greedy approach that chose the interval that ends earliest is not the optimal solution for this problem. We will still order the requests i by increasing finish time. P(j) represents the largest index i<j so that intervals i and j are disjoint !!! what do they mean by disjoint??? !!! (The leftmost interval that ends before j begins). If no request is disjoint from j we set p(j) = 0.
Our solution either includes the last interval, n, or it doesn't!
- If n is in our solution then no interval between p(n) and n is included in the solution (because all of those intervals would overlap with n). So if n is in our solution, our solution is n + the optimal solution of the intervals 1 through p(n).
- If n is not in our solution then our solution is the optimal solution of intervals 1 through n-1.
