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 $.
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.
Solution 2
Sub-problem: after picking one location $ q $, need to find the max revenue of the remaining docks whose location is greater than 5 miles away from $ q $. Bottom-up-dock-revenue.
Let $ r[0...n] $ be a new array, $ r[0]=0 $. The pseudo code is show below:
