# Maximize profit with dynamic programming

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?

• This is a simplified version of portfolio optimization. The model you describe doesn't use the tables themselves, so you can put everything into one single table. – AlexR Mar 27 '15 at 13:18
• I've read about portfolio optimization but I'm still unsure if my recursive formula is correct – Jamgreen Mar 28 '15 at 14:19

## 1 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.
• Thank you! But will this work if I have three tables with different quantities (yielding different profits) for each type of investment and I want to find the best combination of quantities between those three different types of investment? Can I just change $p_j$ to $p_{ij}$ and $c_j$ to $c_{ij}$ where $i$ denotes the investment type? Besides, my homework says that it can be helpful if I let $T_i$ denote the set of possible quantities for each investment type (e.g. $T_2 = \{0,1,2,3,4,5\}$) but I don't know how this is useful. – Jamgreen Mar 28 '15 at 15:34
• I guess I will need a second term in the function $f_{n+1}(A)$. Maybe it's $f_{n+1}(A,i) = \text{max} \{p_{ij} + f_n(A-c_{ij},i-1)\}$? – Jamgreen Mar 29 '15 at 7:17
• @Jamgreen As I noted, the optimization itself doesn't really care about the investment, so you can treat $p_{ij}$ as $p_{\hat j}$ for a renumbered Table containing all three other tables. The set $T$ you mention is basically what the $\max$ is computed over. – AlexR Mar 29 '15 at 9:53
• Oh okay :-) But without denoting the investment type, how can I tell how many objects the firm should invest in each investment type? – Jamgreen Mar 29 '15 at 9:56
• @Jamgreen The index $\hat j$ contains the same information as the pair $(i,j)$. – AlexR Mar 29 '15 at 10:22