Re: Interesting Programming Problem

"Jeff Grippe" <jeff@xxxxxxxxx> wrote:

Thanks in advance for the help.

This is more of a general programming problem rather than a FoxPro problem
but since I work in FoxPro I thought I'd see if any of you had any
interesting ideas. Brute force is probably going to be the way to go,
however.

Yes, it is.

I have a data with amount fields. Lets say that they are in an array because
you wouldn't want to do this against something disk based.

It looks as if you are doing invoice reconciliation or something
similar.

What are the amounts' signs? If it is only one sign, then it is
easier. If there are positive and negative amounts, it is messier.

If there is the possibility of incorrect amounts, it is even
worse. Casting out nines may or may not help.

[snip]

Does anyone have any thoughts on the code for finding all combinations of
one or more amounts that total to a specific value? I know that it is going
to require nested loops but the fact that the solution(s) can be a variable
number of amounts is a bit confusing to me.

For one sign, sort from highest to lowest. Then select the
largest possible value that is not too big and keep doing that as long
as possible. You may find a solution. If not, back off a step, and
try the next possibility. Eventually, you will get through them all.
It will work as in the example below:

Example:
5, 8, 16, 14, 7, 2 with a target of 20

Sorted:
16, 14, 8, 7, 5, 2

Run:
Pick 16. Reject 14, 8, 7, 5. Pick 2. No more data: back off 2. No
more data: back off 16.

Pick 14. Reject 8, 7. Pick 5. Reject 2. No more data: back off 5.
Pick 2. No more data: back off 2. No more data: back off 14.

Pick 8, 7, 5. SOLUTION. If you want all solutions, continue. Back
off 5. Pick 2. No more data: back off 2. No more data: back off 7.
Pick 5, 2. No more data: back off 2. No more data: back off 5. Pick
2. No more data: back off 2. No more data: back off 8.

Pick 7, 5, 2. No more data: back off 2. No more data: back off 5. No
more data: back off 7.

Pick 5, 2. No more data: back off 2. No more data: back off 5.

Pick 2. No more data: back off 2. No more data: end.

Sincerely,

Gene Wirchenko

Computerese Irregular Verb Conjugation:
I have preferences.
You have biases.
He/She has prejudices.
.

Relevant Pages

  • Re: Interesting Programming Problem
    ... This is more of a general programming problem rather than ... a FoxPro problem ... If there are positive and negative amounts, ... sort from highest to lowest. ...
    (microsoft.public.fox.programmer.exchange)
  • Re: Interesting Programming Problem
    ... The problem I have with it is that the amounts I have to add up to the total ... I think it probably going to be best to brute force it ... This is more of a general programming problem rather than a FoxPro problem ... you wouldn't want to do this against something disk based. ...
    (microsoft.public.fox.programmer.exchange)