1
$\begingroup$

You want to visit n cities: $0 → 1 → 2 → · · · → n$.

For traveling between city $i$ and $i + 1$ $(0 ≤ i < n) $ you need to choose between two modes of transportation: train or plane. You are starting at the train station of city $0$ and want to end up at the airport of city $n$.

The cost of transferring between the train station and the airport of city $i$, either direction, is $b_i$. The cost of traveling from city $i$ to city $i+1$ via train is $t_i$ and by plane $p_i$.

You need to use to use the plane and train exactly $n/2$ times. Assume that $n$ is divisible by $2$. Design an $O(n^2)$ dynamic programming algorithm that finds the cost of an optimal solution to the travel planning problem.

What I have so far is what I think is a solution to the problem without considering the $n/2$ constraint.

$Cost(x, i, y) = \begin{cases} \begin{cases}t_i & y=0\\ p_i + b_i & i-y=0 \end{cases} & i=1 \\ min\begin{cases} \begin{cases} min\begin{cases}p_i + Cost(P, i-1,y-1) \\ p_i + b_i + Cost(T, i-1,y-1) \end{cases} & y > 0 \\ inf & y=0 \end{cases} \\ \begin{cases} min\begin{cases} t_i + Cost(T, i-1,y)\\ t_i + b_i + Cost(P, i-1,y) \end{cases} & i-y > 0\\ inf & i-y = 0\end{cases} \end{cases} & 1 < i < 0 \\ min\begin{cases}p_i + Cost(P, i-1,y-1) \\ t_i + b_i + Cost(T, i-1,y) \end{cases} & i=n \end{cases}$

The values of $x$ correspond to different scenarios for which station at $i$ you are located at.

$x = P$

$x = T$

The value of $y$ is the number of plane rides and $i-y$ is the number of train rides $0 \le y \le i$

To get the optimal cost with $n/2$ plane rides you would call $Cost(x,i,\frac{x}{2})$

$\endgroup$
  • 2
    $\begingroup$ What have you tried? Have you considered adding an extra parameter $Cost(x,i,...)$? $\endgroup$ – Tom van der Zanden Jul 26 '15 at 19:21
  • $\begingroup$ I was thinking I could maybe keep track of how many plane trips there were so I could tell if there were n/2 of them, but once I do have n/2 of them I don't know how to keep getting optimal results. $\endgroup$ – guest Jul 26 '15 at 19:27
  • $\begingroup$ Another alternative I'm thinking about is instead of adding the next optimal travel mode, starting with a trip with all trains and adding in plane trips one at a time into their optimal positions. I'm having trouble writing a recurrence relations for this though. $\endgroup$ – guest Jul 26 '15 at 19:31
  • $\begingroup$ I noticed you've edited the question to add your solution, and you seem to want us to check whether your solution is correct. I regret to inform you that "please check my solution" questions are not suitable for this site. They admit only a yes/no answer, which isn't likely to be useful to anyone else (and possibly not even to you). If you are taking a course, you might ask your teaching assistant or grader, but that kind of question is considered off-topic for this site. $\endgroup$ – D.W. Jul 28 '15 at 22:46
  • $\begingroup$ Ok, I'll keep that in mind. Thanks for letting me know. $\endgroup$ – guest Jul 28 '15 at 22:50
2
$\begingroup$

Hint: For each $0 \leq i \leq n$ and $0 \leq t \leq i$, calculate the optimal route between city $0$ and city $i$ using $t$ plane rides and $i-t$ train rides.

$\endgroup$
  • $\begingroup$ So in the end I would have a table of #plane rides vs i with the optimal cost in each cell. Then I could choose the nth cell with n/2 train rides to get the optimal result? $\endgroup$ – guest Jul 26 '15 at 20:41
  • $\begingroup$ This concept is still to vague for me to write a recurrence relation to define it. Writing the how to come up with the optimal route is difficult. $\endgroup$ – guest Jul 26 '15 at 20:48
  • $\begingroup$ What I'm really having trouble with is how to calculate the optimal route with a certain number of plane rides and train rides. $\endgroup$ – guest Jul 26 '15 at 21:08
  • $\begingroup$ @guest now your $Cost(x,i)$ function says - "what is the minimum cost to travel from city 0 to city $i$ and in last city have/haven't transfer of type $x$". Yuval suggest to enhance this dynamic to: $Cost(x,i, t)$ that will answer to question - "what is the minimum cost to travel from city 0 to city $i$ by using exactly $t$ plane rides and $i - t$ train rides and in last city have/haven't transfer of type $x$". $\endgroup$ – knok16 Jul 26 '15 at 21:26
  • 1
    $\begingroup$ @guest It's your exercise, and you have to solve it yourself. $\endgroup$ – Yuval Filmus Jul 26 '15 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.