0
$\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, 1) + M (i_2, 2) + M (i_3, 3) + M (i_4, 4)\}$$

Where $\sum_{s=1}^4 i_s \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$
0
$\begingroup$

You're on the right track. Let's say that $M$ gives the payoff at one single store for a given number of refrigerators (i.e., the value from the table). There's a bit of ambiguity about whether a store can receive zero refrigerators or not. I'll assume the answer is yes (otherwise, the last row of the table is meaningless) and define $M(0, j)=0$ for all $j$.

The recursion function (call it $P(i, j)$) takes as arguments the number $i$ of refrigerators left to allocate (i.e., 7 minus the number already committed) and the "stage" (the store $j$ whose allocation you are currently deciding) and returns the best possible payoff for that store and all remaining stores.

For backward recursion, $P(i, 4)$ = $M(i, 4)$, $P(i, 3) = \max_{k=0}^i \left[M(k, 3) + P(i-k, 4)\right]$, and so on. $P(7, 1)$ gives you the overall optimal objective value.

$\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.