There is a small company which in some months maintains an o

There is a small company which in some months maintains an office in Aukland (code A) and in others in Brisbane (code B), and moves back and forth between these two cities (they can only afford to have one office operating at a time). This company wants to have the cheapest possible location plan - the two cities have different operating costs and these costs can change from month to month.

We are given M, a fixed cost of moving between the two cities, and lists A = (a₁, . . . , a_n) and B = (b₁, . . . , b_n). Here ai is the cost of operating out of Aukland in month i, and b_i is the cost of being in Brisbane that month. Suppose that M = 10, A = (1, 3, 20, 30), and B = (50, 20, 2, 4). If the location plan is (A, A, B, B), its cost will be 1 + 3 + 10 + 2 + 4 = 20. On the other hand, the cost of the plan (B, B, A, B) is 50 + 20 + 10 + 20 + 10 + 4 = 114. The goal here is to (start to) devise a dynamic programming algorithm which, given M, A, and B, determines the cost of the optimal plan. The plan can start in either city, and end in either city. Note that you will likely need two subproblems, which will be mutually recursive.

a) Describe the structure of the subproblem

b) Find a recurrence for the optimal value of the subproblem in terms of smaller subproblems

Solution

Writing a DP alogrithm all the same:

Let C(n) be the total cost of operating after n months.

Recursively defining C(k) = minimum { C(k-1) + a(k) , C(k-1) + M +b(k)    if the city(k-1) = ADX}

                                       minimum { C(k-1) + b(k) , C(k-1) + M +a(k)    if the city(k-1) = BEA}

And then calculate C(n).

This is the overall algorithm to find the cost of operating because, everytime we have to find the best city according to the updated information of Cost of the city in the latest month.