Results 1 to 2 of 2

Thread: Partitioning with Decimals

  1. #1
    Aug 2010

    Partitioning with Decimals

    I have a list of numbers that represent bills due:



    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.

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TriKri's Avatar
    Nov 2006
    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: Jul 22nd 2010, 01:49 PM
  2. partitioning set problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jun 28th 2010, 09:58 AM
  3. Quadratic residues and partitioning
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Mar 29th 2010, 06:13 AM
  4. Replies: 2
    Last Post: Jan 20th 2010, 02:43 PM
  5. Partitioning an open interval
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Nov 1st 2008, 04:53 AM

Search Tags

/mathhelpforum @mathhelpforum