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?

  • $\begingroup$ 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. $\endgroup$ – AlexR Mar 27 '15 at 13:18
  • $\begingroup$ I've read about portfolio optimization but I'm still unsure if my recursive formula is correct $\endgroup$ – Jamgreen Mar 28 '15 at 14:19

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.
  • $\begingroup$ 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. $\endgroup$ – Jamgreen Mar 28 '15 at 15:34
  • $\begingroup$ 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)\}$? $\endgroup$ – Jamgreen Mar 29 '15 at 7:17
  • $\begingroup$ @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. $\endgroup$ – AlexR Mar 29 '15 at 9:53
  • $\begingroup$ Oh okay :-) But without denoting the investment type, how can I tell how many objects the firm should invest in each investment type? $\endgroup$ – Jamgreen Mar 29 '15 at 9:56
  • $\begingroup$ @Jamgreen The index $\hat j$ contains the same information as the pair $(i,j)$. $\endgroup$ – AlexR Mar 29 '15 at 10:22

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.