Maximize profit with dynamic programming

Question

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?

Answer 1

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.