Finding a minimal number of charging stops along the route The question is:
Your electric car needs to be charged every X kilometres. You are doing a road trip from Toronto to Vancouver and have a list of every charging station on the highway between Toronto and Vancouver. For each charging station you know its distance from Toronto. Since it takes an hour to charge the car, you wish to minimize the number of stops along the way.
it is asked to give an algorithm that enable to get from Toronto to Vancouver that minimizes the number stops to charge...
I'm confused how to write the algorithm.
could anyone help me write this algorithm? or give me some hints.
Thanks.
 A: Let $f:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ a function. $f(i,j)$ with $i,j \in \mathbb{N}$ means the minimum number of  stops when we are in station $i$ and we have $j$ kilometres available in our tank. If $n$ is the number of stations and $D_i$ is the distance from Toronto to station $i$ then when we are in an station we can choose do not stop or stop for charge the car, obviously we want to choose the option which minimizes the number of stops. Therefore
$$f(i,j) = \left\{ {\begin{array}{*{20}{c}}
   {1 + f(i + 1,X - \Delta {D_i})} & {} & {i \le n,j < \Delta {D_i}}  \\
   {\min (1 + f(i + 1,X - \Delta {D_i}),f(i + 1,j - \Delta {D_i})))} & {} & {i \le n,j \ge \Delta {D_i}}  \\
   0 & {} & {i = n + 1}  \\
\end{array}} \right.
$$
where $\Delta D_i=D_{i+1}-D_i$ for all $i \in \{1,\cdots n\}$ and we set $D_{n+1}$ as the distance from Toronto to Vancouver. We assume that $X \ge \Delta D_i$ for all $i$, i.e. we can go from one station to next one. Now our answer will be $f(1,X-D_1)$. If you use dynamic programming technique you can compute this in $O(nX)$.
A: This is essentially a basis for an algorithm like one by which $\TeX$ chooses an optimal sequence of points to break a paragraph into lines (although that has a lot of bells and whistles that do not concern us here). The basic idea is to consider the potential stops $S$ in order (I assume you list is already sorted by distance from Toronto, otherwise do that first), and to find for each the optimal sequence of stops leading to a stop at $S$. This is merely a question of traversing all  station before $S$ but no further than $X$ kilometers from $S$, selecting one $S'$ that was found to require the fewest number of stops to arrive at it, and choosing the optimal sequence to $S$ to be the optimal one for $S'$ followed by a trip directly from $S'$ to $S$. To get the algorithm going, the starting point should be considered a stop requiring $0$ intermediate stops; the arrival is also a stop and its optimal sequence is the desired result.
It is not necessary to record for each potential stop a complete list of previous stops forming a sequence to it; just recording the before-last stop $S'$ of that sequence and the total number of stops (for comparison) suffices.
A more generalised version of such an algorithm, which in addition takes into account a cost that may be associated to passing form $S'$ to $S$ (depending on that pair of points) is known after its inventor as Dijkstra's algorithm.
A: The following greedy approach works:
1 . Start your trip in Toronto with a full charge.
2 . Determine the farthest away charging station in your route within X Kilometers. Stop at that charging station, charge up your car .
3 . Again determine the farthest away charging station in your route within X Kilometers from this stop.
4 . Repeat the process until you get to Vancouver.
http://web.cs.wpi.edu/~cs2223/b05/Exams/Quiz2/
