| Line 36: | Line 36: | ||
<math> | <math> | ||
| − | |||
\KwData{river stretch $L$, possible sites for docks:$x_1, x_2, x_3, ..., x_n$ , the possible revenue for each dock: $r_1, r_2, r_3, ..., r_n$ } | \KwData{river stretch $L$, possible sites for docks:$x_1, x_2, x_3, ..., x_n$ , the possible revenue for each dock: $r_1, r_2, r_3, ..., r_n$ } | ||
\KwResult{The subset of docks that yields the greatest total revenue, with the restriction that the distance between each two docks are no less than 5 miles } | \KwResult{The subset of docks that yields the greatest total revenue, with the restriction that the distance between each two docks are no less than 5 miles } | ||
| Line 62: | Line 61: | ||
} | } | ||
\caption{Find the subset of docks with maximum revenue} | \caption{Find the subset of docks with maximum revenue} | ||
| − | |||
</math> | </math> | ||
In the end of the program, <math>R[n]</math> will be the maximum revenue, and L[n], L[L[n]], ... will be the indices of locations to choose. | In the end of the program, <math>R[n]</math> will be the maximum revenue, and L[n], L[L[n]], ... will be the indices of locations to choose. | ||
Revision as of 17:36, 20 July 2017
Computer Engineering(CE)
Question 1: Algorithms
August 2013
Solution 1
This problem can be solved using dynamic programming. For each docks $ x_i $, compute the revenue from $ x_1 $ to $ x_i $, if $ x_i $ is selected, and the remaining docks $ x_{i+1} $ to $ x_n $, if $ x_i $ is not selected.
$ R[i] $: denote the total revenue using only sites $ x_1, \dots , x_i $.
$ L[i] $: denote $ i $ with the greatest value such that $ x_i $ is used for the solution in $ R[i] $.
Initially, $ L[<=0]=0 $, $ R[<=0]=0 $, $ x_0 = -\infty $, $ r_0=0 $. The pseudo code for dynamic programming is showing below. Note we use bottom up to fill up $ R $ and $ L $.
Caption1
$ \KwData{river stretch $L$, possible sites for docks:$x_1, x_2, x_3, ..., x_n$ , the possible revenue for each dock: $r_1, r_2, r_3, ..., r_n$ } \KwResult{The subset of docks that yields the greatest total revenue, with the restriction that the distance between each two docks are no less than 5 miles } initialization: $L[<=0]=0$, $R[<=0]=0$, $x_0 = -\infty$, $r_0=0$\; \For {$i = 1$ to $n$}{ read $x_i$\; \eIf{$|x_i-x_{L[i-1]}| >=5$}{ $R[i]=R[i-1]+r_i$\; $L[i]=i$\; }{ \For {$k=i-1$ down to $1$}{ \If{$|k_k - x_i| >=5$}{ \eIf{$R[k]+r_i > R[i-1]$}{ $R[i]=R[k]+r_i$\; $L[i]=i$\; } {$R[i]=R[i-1]$\; $L[i]=L[i-1]$\; } Break; } } } } \caption{Find the subset of docks with maximum revenue} $
In the end of the program, $ R[n] $ will be the maximum revenue, and L[n], L[L[n]], ... will be the indices of locations to choose.
