Solution Found!
Yuckdonalds is considering opening a series of restaurants along Quaint Valley Highway
Chapter 6, Problem 6.3(choose chapter or problem)
Yuckdonald’s is considering opening a series of restaurants along Quaint Valley Highway (QVH).The \(n\) possible locations are along a straight line, and the distances of these locations from the start of QVH are, in miles and in increasing order, \(m_{1}, m_{2}, \ldots, m_{n}\). The constraints are as follows:
At each location, Yuckdonald’s may open at most one restaurant. The expected profit from opening a restaurant at location \(i\) is \(pi\), where \(p_{i}>0\) and \(i=1,2, \ldots, n\).
Any two restaurants should be at least \(k\) miles apart, where \(k\) is a positive integer.
Give an efficient algorithm to compute the maximum expected total profit subject to the given constraints.
Questions & Answers
QUESTION:
Yuckdonald’s is considering opening a series of restaurants along Quaint Valley Highway (QVH).The \(n\) possible locations are along a straight line, and the distances of these locations from the start of QVH are, in miles and in increasing order, \(m_{1}, m_{2}, \ldots, m_{n}\). The constraints are as follows:
At each location, Yuckdonald’s may open at most one restaurant. The expected profit from opening a restaurant at location \(i\) is \(pi\), where \(p_{i}>0\) and \(i=1,2, \ldots, n\).
Any two restaurants should be at least \(k\) miles apart, where \(k\) is a positive integer.
Give an efficient algorithm to compute the maximum expected total profit subject to the given constraints.
ANSWER:
Step 1 of 3
Suppose array P[i] contains the profit at location \(i\)
And array EP[i] contains the maximum expected profit at location \(i\)
\(\operatorname{fun}\left(m_{i}, m_{j}\right)\) returns the value 0 if \(m_{i}-m_{j}<k\) and returns 1 if \(m_{i}-m_{j}>k\)