Results 1 to 4 of 4

Math Help - Find ways to invest money

  1. #1
    Newbie
    Joined
    Nov 2011
    Posts
    2

    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.
    Last edited by justsof; November 21st 2011 at 12:04 PM. Reason: typos
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Find ways to invest money

    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 v_i equal weights w_i.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2011
    Posts
    2

    Re: Find ways to invest money

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie JovanyBroden's Avatar
    Joined
    Oct 2012
    From
    Chicago, Illinois, USA
    Posts
    1

    Re: Find ways to invest money

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 5th 2011, 09:16 PM
  2. Find Percentage of Money
    Posted in the Algebra Forum
    Replies: 7
    Last Post: October 5th 2010, 11:09 AM
  3. Find Money Earned By Magazine
    Posted in the Algebra Forum
    Replies: 4
    Last Post: October 5th 2010, 10:30 AM
  4. Replies: 3
    Last Post: December 14th 2008, 10:04 AM
  5. Find amount of money
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 28th 2007, 06:17 PM

Search Tags


/mathhelpforum @mathhelpforum