Describe the structure of the subproblem

Assignment Help Computer Engineering

Reference no: EM132132965

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 = (a1, . . . , an) and B = (b1, . . . , bn).

Here ai is the cost of operating out of Aukland in month i, and bi 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.

Reference no: EM132132965

Questions Cloud

Time on the internet on the phone : In a sample of 12 kids, their mean time on the internet on the phone was 3.9 hours with a standard deviation of 0.7 hours.

Sample standard deviation : Want the 98% confidence interval when the sample size is 50, sample mean is 42 and sample standard deviation is 5. Keep three decimal places in your response.

How this technology can be used effectively in a business : Describe how this technology can be used effectively in a business setting. Are there any drawbacks to using social networks in a business setting?

Write a class that implements this interface : Write a class that implements this interface while not using any number type member variables (e.g., int, float, etc).

Describe the structure of the subproblem : Find a recurrence for the optimal value of the subproblem in terms of smaller subproblems.

Which web site is your favorite : Which site would you recommend or use to help a small business wanting to get into e-commerce? Why?

Which is violated in context which may not be appropriate : Identify at least one LP assumption which is violated in this context which may not be appropriate when the decision variables relate to number of storage units

How do you go about adding an alert : How do you go about adding an alert (both setting up a new alert and adding one to a monitored system)?

How can it be used to create a sourcing plan : What is employee profiling? How can it be used to create a sourcing plan?

User Account

All Pages