Dynamic programming

Hide text Hide pseudo-code
The task is to schedule n events in such a way that there is no overlapping events and the combined profit is maximum. Use the following algorithm.

The input contains the events and the corresponding profits. The output is the optimal combined profit in Result[0] (for the selected events in Select table).

  • Input: tables Begin[0..n-1], End[0..n-1] (start and end times of events), Profit[0..n-1] (the earnings if this event was selected), and the number of events n
  • Output: tables Select[0..n-1] (true or false depending on whether this event was selected or not, respectively), and Result[0..n] (for each index i, this denotes the cumulative profit for events i..n; note that the result table is larger than the rest of the tables on purpose)
 1 SelectEvents(Begin, End, Profit, n) {
 2    Result[n-1] = Profit[n-1];
 3    Select[n-1] = TRUE;
 4    for (int i=n-2; i>=0; i--) {
 5        j = earliest event such that Begin[j] >= End[i] or j = n;
 6        if (Profit[i] + Result[j] >= Result[i+1]) {
 7            Select[i] = TRUE;
 8            Result[i] = Profit[i] + Result[j];
 9        } else {
10            Select[i] = FALSE;
11            Result[i] = Result[i+1];
12        }
13    }
14    clear overlapping true values from select table, i.e., starting from
15    beginning (i=0), if there exists such an event i+k, k>0 that overlaps 
16    with event i then event i+k is set false in select table.
17 }

  Created Fri Oct 30 13:52:50 EET 2009 - Powered by SVG-hut