Question

You are going on a long trip. You start on the road at mile post $0$. Along the way there are$n$ hotels, at mile posts $a_1<a_2<...<a_n$ , where each$a_i$ is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance $a_n$), which is your destination. You’d ideally like to travel miles a day, but this may not be possible (depending on the spacing of the hotels). If you travel x miles during a day, the penalty for that day is ${\left(200-x\right)}^{\mathbf{2}}$. You want to plan your trip so as to minimize the total penalty- that is, the sum, over all travel days, of the daily penalties.Give an efficient algorithm that determines the optimal sequence of hotels at which to stop

Short answer

Dynamic programming provides an efficient algorithm to determine the optimal sequence of hotels.

Step-by-step solution

Introduction to Dynamic programming

Dynamic programming helps to solve the problems that can be divided into subproblems and the solution of subproblems is used to calculate the optimal solution of the problem. Dynamic programming obtains both local and global optimal solution.

Determine the approach for efficient algorithm to find optimal sequence of hotels

The objective of the algorithm is to reduce the penalty.

Consider $OP\left(i\right)$as the minimum total penalty to reach hotel $i$. Before reaching hotel $i$, keep the track of all hotels$j$ which can be used to stay. So, the minimum penalty to reach hotel$i$ is the sum of minimum penalty to reach hotel ‘$j’$’ and the cost of trip from$j$ to$i$ is ${\left(200-\left(a_j-a_i\right)\right)}^2$.

Thus, $OP\left(i\right)=\text{MIN}\left(OP\left(j\right)+{\left(200-\left(a_j-a_i\right)\right)}^2\right)$.

The base value is $OP\left(0\right)=0$because$i=0$ is the starting point of the trip. Call the function recursively within the loop to get minimum penalty to reach hotel $n$.

Determine the algorithm to find the optimal sequence of hotels

The algorithm to find the optimal sequence of hotels is as follows:

$\begin{array}{l}OP\left(0\right)=0\\ \text{for}\left(i=0\text{\hspace{0.33em}to\hspace{0.33em}}n\right)\\ OP\left(i\right)=\text{MIN}\left(OP\left(j\right)+{\left(200-\left(a_j-a_i\right)\right)}^2\right)\text{\hspace{0.33em}for\hspace{0.33em}}j=0\text{\hspace{0.33em}to\hspace{0.33em}}i-1\\ \text{return\hspace{0.33em}}OP\left(n\right)\end{array}$

Thus, the algorithm returns the minimum penalty