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