| Line 19: | Line 19: | ||
August 2013 | August 2013 | ||
</center> | </center> | ||
| + | ---- | ||
| + | '''Problem 2.''' | ||
| + | |||
| + | Suppose your company develops and manages construction of boat launching docks along a downstream stretch of the Wabash river. This stretch runs north-south for <math>L</math> miles within the State of Indiana. The possible sites for docks are given by numbers <math>x_1 < x_2 < x_3 < ... < x_n</math>, each in the interval <math>[0,L]</math>, specifying their positions in miles measured from the northern end of this stretch of the Wabash river. If your company constructs a dock at position <math>x_i</math>, it receives a revenue of <math>r_i >0</math>. Regulations imposed by the Indiana Department of Water Resource Management require that no two docks should be built within a distance of less than 5 miles from each other. Your company plans to construct docks at a subset of the potential sites so as to maximize the total revenue., subject to this distance restriction. For example, suppose <math>L=20</math> and <math>n=5</math> with potential sites given by <math>\lbrace x_1, x_2, x_3, x_4, x_5 \rbrace = \lbrace 6,7,12,13,14\rbrace</math> and <math>\lbrace r_1, r_2, r_3, r_4, r_5 \rbrace = \lbrace 5,6,5,3,1\rbrace</math>. Then the best solution is to construct docks at locations <math>x_1</math> and <math>x_3</math> to achieve a revenue of 10. | ||
| + | Describe a dynamic programming formulation to find a solution for this optimization problem. Compute the complexity of solving your dynamic programming formulation of this problem. | ||
| + | |||
| + | ---- | ||
| + | |||
---- | ---- | ||
===Solution 1=== | ===Solution 1=== | ||
Revision as of 19:25, 21 August 2017
Computer Engineering(CE)
Question 1: Algorithms
August 2013
Problem 2.
Suppose your company develops and manages construction of boat launching docks along a downstream stretch of the Wabash river. This stretch runs north-south for $ L $ miles within the State of Indiana. The possible sites for docks are given by numbers $ x_1 < x_2 < x_3 < ... < x_n $, each in the interval $ [0,L] $, specifying their positions in miles measured from the northern end of this stretch of the Wabash river. If your company constructs a dock at position $ x_i $, it receives a revenue of $ r_i >0 $. Regulations imposed by the Indiana Department of Water Resource Management require that no two docks should be built within a distance of less than 5 miles from each other. Your company plans to construct docks at a subset of the potential sites so as to maximize the total revenue., subject to this distance restriction. For example, suppose $ L=20 $ and $ n=5 $ with potential sites given by $ \lbrace x_1, x_2, x_3, x_4, x_5 \rbrace = \lbrace 6,7,12,13,14\rbrace $ and $ \lbrace r_1, r_2, r_3, r_4, r_5 \rbrace = \lbrace 5,6,5,3,1\rbrace $. Then the best solution is to construct docks at locations $ x_1 $ and $ x_3 $ to achieve a revenue of 10. Describe a dynamic programming formulation to find a solution for this optimization problem. Compute the complexity of solving your dynamic programming formulation of this problem.
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:
