[Math] Maximize profit with dynamic programming

dynamic programmingoptimizationrecursionrecursive algorithms

I have 3 tables…

$$\begin{array}{rrr}
\text{quantity} & \text{expense} & \text{profit}\\
\hline
0 & 0 & 0 \\
1 & 100 & 200 \\
2 & 200 & 450 \\
3 & 300 & 700 \\
4 & 400 & 1000
\end{array}
\qquad
\begin{array}{rrr}
\text{quantity} & \text{expense} & \text{profit}\\
\hline
0 & 0 & 0 \\
1 & 100 & 220 \\
2 & 200 & 480 \\
3 & 300 & 800 \\
\end{array}
\qquad
(\cdots)$$

All equal structure but with different values and different number of rows.

I want to write a recursive function describing the optimal choices of quantities in order to maximize my profit.

I have a given amount to spend and the total expenses can't exceed this.

Besides, I use the notation that $p_{nj}$ should the profit in table $n$ and quantity $j$ and $c_{nj}$ should express the cost of choosing quantity $j$ in table $n$.

I think it's something like

$$
f_n(A) = \text{max} \left[p_{nj} + f_{n+1}\left(A-c_{nj}\right)\right]
$$
where $A$ is the amount I can invest.

My intuition is that I'm adding the profit $p_{nj}$ for each iteration and subtracting the cost from the total available amount ($A-c_{nj}$).

I don't think it's correct but I guess it's something like that. How can I iterate through all the three different tables with recursion?

Best Answer

If $f_n(A)$ gives the maximum profit from taking at most $n$ objects and at most $A$ cost, the maximum profit for at most $n+1$ objects costing at most $A$ must be $$f_{n+1}(A) = \max_j \{ p_j + f_n(A-c_j) \mid c_j \le A \} \cup \{0\}$$ Note that we

  • Maximize over all objects that we could chose. If we can't chose any object within budget, the maximum profit is obtained by chosing nothing ($0$).
  • Constrain the objects we try to add to only those objects still within budget.
  • $f_{n+1}(A)$ depends on $f_n(A)$, not the other way around.
  • $f_0(A) = 0$ for any $A$, since no objects equals no profit.
Related Question