Question

You are going on a cross-country road trip. You know the route you will take. There are n hotels along this route. You know the location and rate rj for each hotel hj along the route, for 1 ≤ j ≤ n.   You also know the distance dj of each hotel from your starting point. You will eventually get to your destination, after traveling a distance d*.    You can travel a maximum of m miles in a day.
You want to minimize the total cost of lodging on your trip of distance d*, call this total cost roomCost(d*). Write an equation for the recursive solution to this problem, by steps.

a) There will be some hotel hj that is the last hotel you will stop at before your destination. Not all hotels are candidates to be this last hotel. What inequality relates the distance dj from the starting point to this last hotel, and the distance d*?


b) Given that you stop for the last night at hotel hj, at a distance dj from your starting point, for a cost of rj, what is the recursive equation for the total room cost for all the previous nights (if any)?
This will be of the form roomCost(dn+1) = <something>


c) What is the recursive equation for minimizing the overall cost roomCost(dn+1)? In other words, take the equation in part b and minimize it over the appropriate variable(s).

Answer 1

a.

As d_j is the last halting point, destination d* to d_j can be m at most, i.e the daily travelling limit.

b. The total cost roomCost(d_n +1) , will be the sum of last day cost r_j and cost till the previous day i.e. roomCost(d_n)

c.

-------------------------END---------------------

Please give a thumbs up(upvote) if you liked the answer.