Dynamic programming Santa Cruz has finally given into corporate pressure and is

Question

Dynamic programming

Santa Cruz has finally given into corporate pressure and is now allowing yet another Big-Chain
Restaurant Company to open up several restaurants in town.
The chain has identified one main street where it wants to open up its restaurants, which is divided
into n distinct blocks. After some Evil Corporate Number Crunching, the company has estimated
that it will earn a profit of P(i) from opening a restaurant in block i.
However, there’s one catch. Due to an old zoning law, the restaurants have to be at least d blocks
away from each other. So, if we put a restaurant on block j, we can’t open restaurants at blocks
j - d, j - d + 1,..., j - 2, j - 1, j + 1, j + 2,..., j + d - 1, j + d.
Your job is to figure out the maximum possible profit that the company can attain.

1. Write a mathematically correct recursive property of the OPT value that you are trying to compute.
2. Explain carefully why the recursion holds. If you do this well, what you write will read as self-evident.
3. Explain carefully the data structure you will use to store the OPT value for the different subproblems and the
order in which you will fill out the entries in your data structure, per the enablement of the recursive property.
4. Where needed, state the additional information you can record which, along with a proper “backtracing”
method, will allow you to report an optimal solution, as opposed to just the value of OPT.
5. Bound the total time of your algorithm by bounding the size of the data structure and the work per entry in it.

Explanation / Answer

1)
since the sequence is seemed to like Arthimetic expression..
Since we have differnce is common between all data .. with divided with equal difference.

It is in the form :
(a - (n-1)d) + (a - (n-2)d) + ...
So we can recursive property will be (a - (n-1)d)

----------------------------------------------------------------------------------------------
2)
Since at every block we have to calculate corresponding profit value to get thr gross
profit, so we repeat the same process to 'n' blocks. So recursion occurs. Individual restaurant can be
accessed using object getter setter methods.
----------------------------------------------------------------------------------------
3)
I will use ArrayList which contains the all restaurant objects.
So while listing or calculating values... then we can get the informatoin via object getter and
setter methods.

------------------------------------------------------------------------------------------------------
4) While backtracking, it is better to hold the value of profit at each step, as our
ultimate goal is to earn more profits. So, store profit value. It will helps to backtrack at correct position and
can continue from there for next step.
---------------------------------------------------------------------------------------------------------
5)
Since we track and each restaurant and again come back to backtrack.. so there were a lot of comparisions.
To say simple.. we check each restaurant with all other possible frequent sets with other restaurants.
So complexity will be O(n!)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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