Results 1 to 2 of 2

Math Help - Partitioning with Decimals

  1. #1
    Newbie
    Joined
    Aug 2010
    Posts
    1

    Partitioning with Decimals

    I have a list of numbers that represent bills due:

    i.e.:

    224.05
    200.35
    137.29
    162.20
    27.00

    but a client might only send in a check for $388.34 and not say which invoices it is for.

    Is there a way of determining which numbers in this list add up to 388.34?

    This is a very simple example, the real list can be as long as 200 different invoice amounts.

    I'm writing software so any programming classes or ideas you know that can help with this would be appreciated.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    I don't think that there is any efficient algorithm to determine which of the invoices the client desires to pay for; I would assume that the problem can't be solved in polynomial time. It is very similar to the subset sum problem, which is NP-complete, i.e. there is no known efficient way to calculate a solution for the problem (NP), and it is at least as hard to solve as the hardest problem for which a solution can be verified in polynomial time (NP-hard).

    I would suggest that the client instead gets to choose which of the invoices to pay for.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. partitioning/multinomial coefficients
    Posted in the Statistics Forum
    Replies: 1
    Last Post: July 22nd 2010, 01:49 PM
  2. partitioning set problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 28th 2010, 09:58 AM
  3. Quadratic residues and partitioning
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 29th 2010, 06:13 AM
  4. Replies: 2
    Last Post: January 20th 2010, 02:43 PM
  5. Partitioning an open interval
    Posted in the Calculus Forum
    Replies: 2
    Last Post: November 1st 2008, 04:53 AM

Search Tags


/mathhelpforum @mathhelpforum