Question

Yuckdonald’s is considering opening a series of restaurant 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,${\mathbf{m}}_{\mathbf{1}}\mathbf{,}\mathbf{m}{\mathbf{2}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathbf{m}}_{\mathbf{n}}\mathbf{.}$. The constraints are as follows:

At each location, Yuckdonald may open at most one restaurant. The expected profit from opening a restaurant at location i is given as${\mathbf{p}}_{\mathbf{i}}$, where${\mathbf{p}}_{\mathbf{i}}\mathbf{>}\mathbf{0}$and$\mathbf{i}\mathbf{=}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{\dots }\mathbf{,}\mathbf{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.

Short answer

In this question certain thing we need to notice,

• “At each location, Yuckdonald may open at most one restaurant”.

This means either no restaurant or at most one restaurant can be opened in each location.

• “Any two restaurants should be at least k miles apart, where k is a positive integer”.

This means if suppose there are two location and, then each restaurant can be open only if:

$\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\mathbf{\left(}{\mathbf{m}}_{\mathbf{n}}\mathbf{\right)}\mathbf{-}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\mathbf{\left(}{\mathbf{m}}_{\mathbf{m}}\mathbf{\right)}\mathbf{>}\mathbf{=}\mathbf{k}$

Step-by-step solution

Defining base condition and constraints mathematically

Let us suppose$P\left(i\right)$be the maximum profit Yuckdonald can fetch from restaurants that are open in location from 1 to i.

So if$i=0$, this implies that there is no location available to open a restaurant.

Thus$P\left(0\right)=0$i.e., Profit is 0 as no restaurant is open.

So based on our constraints we will define a recursion relation,

$\mathit{P}\mathbf{\left(}\mathit{i}\mathbf{\right)}\mathbf{=}\mathit{M}\mathit{A}\mathit{X}\{\begin{array}{l}\left(MA{X}_{i<j}\right(P\left(j\right)+\beta (m_i,m_j).p_i)\\ p_i\end{array}$

Here,

role="math" localid="1657267434540" $\mathbf{P}\mathbf{\left(}\mathbf{j}\mathbf{\right)}\mathbf{=}\mathbf{}\mathit{M}\mathit{a}\mathit{x}\mathit{i}\mathit{m}\mathit{u}\mathit{m}\mathbf{}\mathit{p}\mathit{r}\mathit{o}\mathit{f}\mathit{i}\mathit{t}\mathbf{}\mathit{o}\mathit{b}\mathit{t}\mathit{a}\mathit{i}\mathit{n}\mathbf{}\mathit{f}\mathit{r}\mathit{o}\mathit{m}\mathbf{}\mathit{l}\mathit{o}\mathit{c}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\mathbf{}\mathbf{‘}\mathbf{j}\mathbf{’}\mathbf{}$

But if profit obtain from location ‘i’ is more then location ‘j’ or if it’s not possible to locate restaurant at location ‘j’, then ‘$p_i$’ will be our maximum profit.

Here, symbol $\beta$will define whether there can be a restaurant at location i .

So we define$\beta$as:

$\mathbf{\beta }\mathbf{=}\{\begin{array}{l}0;\mathrm{if}(m_i-m_j)<k\\ 1;\mathrm{if}(m_i-m_j)>k\end{array}$

Implement the algorithm

We will initiate an array$Profit[]$that will tell about expected profit from location ‘i’

Here, v variable will store temporary value of$Profit\left[i\right]$ .

$$\begin{gathered} fori=1toN \\ Profit\left[i\right]=0 \\ fori=2toN \\ forj=1toi-1 \\ v=\left(Profit\right[j]+\beta (mi,mj).P[i\left]\right) \\ ifv>Profit\left[i\right] \\ v=Profit\left[i\right] \\ ifProfit\left[i\right]<P\left[i\right] \\ Profit\left[i\right]=P\left[i\right] \end{gathered}$$

Since two loops are executing here, so collectively the time complexity is $O\left(n^2\right)$.