1
$\begingroup$

I have this problem to resolve in dynamic programming:

An ice cream shop owner has 4 stores. To meet the demand in the summer he purchased 7 refrigerators for the ice cream. Because the stores are in different places, there are different points for selling the ice cream. It was estimated the profit (in monetary unit) that could be obtained in each store:

$$ \begin{array}{c|lcr} N refrigerators & \text{store1} & \text{store2} & \text{store3} & \text{store4} \\ \hline 1 & 4 & 2 & 6 & 1 \\ 2 & 6 & 6 & 12 & 4 \\ 3 & 10 & 8 & 14 & 8 \\ 4 & 12 & 10 & 18 & 16 \\ 5 & 14 & 12 & 20 & 20 \\ 6 & 16 & 16 & 22 & 21 \\ 7 & 18 & 20 & 22 & 24 \end{array} $$

The problem asks to find the working scheme that maximizes the financial return.

As dynamic programming aims to reuse the code I know that it is necessary to use a recursive function, but when analyzing the problem I assumed that my answer field is in a matrix where the lines are referring to the number of refrigerators and the columns the stores.

Then I assumed that $M(i, j)$ is my function that returns a monetary value, assuming that $i$ is the number of refrigerators, ranging from $1 \le i \le 7$, and $j$ is a particular store, ranging from $1 \le j \le 4$.

I also assumed that my function would have 4 calls of this same function $M(i, j)$, because there are 4 stores to divide 7 refrigerators:

The equation would be:

$$MAX \{ M(i, 1) + M (i, 2) + M (i, 3) + M (i, 4)\}$$

Where $\sum_{i=1}^4 i \le 7$

As a base case of recursion I put this:

$$M(0, 1) + M (0, 2) + M (0, 3) + M (0, 4) = 0$$

But my problem is not knowing how to treat this problem recursively. Maybe I'm doing the wrong analysis, too. Every help is welcome.

$\endgroup$
1
$\begingroup$

In this particular case, you can just go over all possibilities.

The dynamic programming approach is to compute recursively the maximal profit that can be obtained from using $x$ refrigerators in the first $y$ stores (and not using any in the other stores). I'll let you fill in the missing details.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.