Thread: Find ways to invest money

I have this problem where I want to find all the ways one can invest money over several items. I am doing this for a game and I thought it was an easy problem but I am stuck since it is not that easy...
Basically the problem is this:

You have a certain amount of money RP (specifically RP = 1360)
Find all the sets of items that you can buy with this RP.
For this specific example there are 6 items to buy, you can buy the same item more than once.
Item prices (for example): (975,520,487,260,244,130)
So for example, two distributions would be:
(0,0,0,0,0,10)
(0,0,0,1,0,8)

How do I solve this problem, possibly by writing a small code.

Thanks for your time.

Welcome to the forum.

I am not aware of a neat mathematical formula. You could try dynamic programming: for each intermediate amount 0 <= A <= 1360 in turn you find and store the sets of items you can buy with A, and you find the corresponding sets for A + 1 by subtracting the price of each item from A + 1 and looking up the corresponding distributions. For example, if you generated the distributions for all A <= 1000, you consider distributions for 1001 - 975 and add the first item to them, distributions for 1001 - 520 and add the second item to them, etc. It makes sense to divide the numbers by the greatest common divisor first. Alternatively, you could consider all possible multisets of items up to certain cardinality and eliminate those that go over the total amount or allow adding another item.

Both methods above take exponential time, but it is possible that there is no way around it, at least when all numbers are integers. If you generate all distributions, then you can also find the distributions with the highest amount under the given limit. Finding such highest amount is known as an unbounded knapsack problem where values equal weights .

Thank you emakarov,
I really like the suggestions you made and the information about the knapsack problem. I was surprised to find such complexity behind the problem. Anyway, I will implement one of your suggested methods tonight and see where I end up =). Thanks once again.

To add more info about money investment, when you invest money in company stock, commodities, and other venues, the hope is that you will enjoy sensible return on your cash, perhaps even high returns. However, investment fees can creep in and eat away at the gains. Pay attention, and you can learn the way to save money on investing charges. Read more here