Re: Interesting Programming Problem

for this particular case (searching for a specific total)
it is better to sort in ascending order, that way you stop
when sum > total
in your example, 10 checks vs 17 (depending how you count)

al


"Gene Wirchenko" <genew@xxxxxxxx> wrote in message
news:mnjo34po7k8funr1esl5eldbhi6ni0b0k3@xxxxxxxxxx
"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, ...
    (microsoft.public.fox.programmer.exchange)
  • Re: Sorting algorithms was: Factorial
    ... > approaching 2GB as soon as a year from now. ... What advantage is there to keeping such large amounts of data, ... file in an index file that would be used when adding later data. ... you don't need to sort for every ...
    (microsoft.public.vb.general.discussion)
  • Print infoirmartion from excel to text document
    ... sheet....i have created macros to sort the information and to calculate ... amounts out in a plain text document for transfer to my betting ... text document with out spaces or predifined spaces in this format ...
    (microsoft.public.excel)
  • Re: Formula Help
    ... Sort your range by the order number column. ... This'll give you a new line with just the subtotals. ... > I have a spreadsheet that lists various order numbers on multiple rows ... > with different amounts for that order. ...
    (microsoft.public.excel.worksheet.functions)
  • Re: To increase speed on manipulating big arrays in Java with minimal bounds checking, ...
    ... > This sort of low level optimisation is not something to be concerned ... Unless, of course, you are manipulating large amounts of data and the ...
    (comp.lang.java.programmer)