Difference between revisions of "ECE PhD QE CE 2013 Problem1.2" - Rhea

Revision as of 17:36, 20 July 2017

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

$ \begin{algorithm}[H] \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} \end{algorithm} $ 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.

Back to QE CE question 2, August 2013

Back to ECE Qualifying Exams (QE) page