Problem Detail: 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 minbegin{cases} begin{cases} minbegin{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} minbegin{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 = 0end{cases} end{cases} & 1 < i < 0 minbegin{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})$
Asked By : guest
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/44758
