There is a small company which in some months maintains an office in Portland (c

Question

There is a small company which in some months maintains an office in Portland (code PDX)
and in others in Seattle (code SEA), and moves back and forth between these two cities (they
can only afford to have one oce 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 xed cost of moving between the two cities, and lists P = (p_1,....,p_n) and
S = (s_1,...,p_n). Here p_i is the cost of operating out of Portland in month i, and s_i is the cost
of being in Seattle that month. Suppose that M = 10, P = (1; 3; 20; 30), and S = (50; 20; 2; 4).
If the location plan is (PDX, PDX, SEA, SEA), its cost will be 1+ 3+ 10+ 2+ 4 = 20. On the
other hand, the cost of the plan (SEA, SEA, PDX, SEA) is 50 + 20 + 10 + 20 + 10 + 4 = 114.

The plan can start in either city, and end in either city. Describe the structure of the subproblem and find a recurrence relation for the optimal value of the subproblem in terms of smaller subproblems.

Explanation / Answer

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) + p(k) , C(k-1) + M +s(k)    if the city(k-1) = PDX}

                                       minimum { C(k-1) + s(k) , C(k-1) + M +p(k)    if the city(k-1) = SEA}

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.

//Pm me if you need further help

//Cheers!!

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.