# Maximizing profit (dynamic programming)

I'm looking at a dynamic programming question and can't figure out how to solve it. The question is listed at the following website (question number 19, towards the bottom).

http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf

The question asks to find the optimal allocation of the budget among the 5 products.

I don't really know how to start the problem, but this is what I have thought so far:

The goal is to find a combination from the 5 products such that the profit is highest. Now, the number of possible combinations seems extremely large:

You can allocate all funds to product A and get 0.98 profit. You can allocate 900,000 funds to product A, 100,000 funds to product B ... and so on

But the number of cases is too large to check 1 by 1. So there must be a faster way.

So how do I actually solve this problem?

• Guess you need to first read about dynamic programming before solving exercises. Did you manage to solve all (or most) of questions 1 to 18, before attempting question 19? – ShreevatsaR Apr 15 '15 at 4:26
• I have looked at simple, elementary examples. But I am interested in this question, not 1-18. – AAKK Apr 15 '15 at 4:33
• More precisely: how many of questions up to 18 did you solve? Why attempt 19? – ShreevatsaR Apr 15 '15 at 4:38