[centipede]

Hi there,

I'm not a programmer but was wondering if anyone knows if it is possible to write a program (eg. VB in Excel) so that you can input a long list of numbers in one column and then another number that is the total of SOME of those numbers in another field, and then have the formula tell you which of the numbers in that list go together to make the total? We have had some amateur VB users here try to create such a calculator, without success. Any ideas would be greatly appreciate.

email: Removed e-mail
thanks!

[Advertisements]

Hi centipede,

Wow, sounds very weirdy, why do you need that? Maybe we can come up with a different approach to the problem. Please, also hint me on the title: " VB number permutation calculator" - I don't seem to get the connection between that and the post and we'll see what can be done about this

Edited by Hai Mac, 11 July 2006 - 03:56 AM.

[Hai Mac]

Hi centipede,

Wow, sounds very weirdy, why do you need that? Maybe we can come up with a different approach to the problem. Please, also hint me on the title: " VB number permutation calculator" - I don't seem to get the connection between that and the post and we'll see what can be done about this

Edited by Hai Mac, 11 July 2006 - 03:56 AM.

[Swandog46]

Can't be done. This problem can't be solved uniquely, UNLESS you can settle for ANY subset of numbers that will make the given sum. And even THAT problem is NP-complete.

Example: consider the following list of numbers:

1, 2, 4, 6, 7

If I tell you the subset sum is 10, you can make that two ways: 1+2+7, or 4+6. How would the program choose which one to return?

Now suppose all you demand is that the program return ANY subset of numbers that sums to your given total. Then the problem can be solved (though not uniquely), but this reduces exactly to a canonical problem in algorithms / theoretical computer science, the Subset Sum Problem. See:
http://en.wikipedia....set_sum_problem

This problem is part of a class of problems known as the "NP-complete" problems.
http://en.wikipedia....iki/NP-complete
http://en.wikipedia....lasses_P_and_NP

I am not going to try to explain in brief terms what NP and NP-complete problems are (if you DO want to hear this, let me know), but suffice it to say that classifying a problem as NP-complete is tantamount to proving that it is among the hardest problems we know. We know of no efficient solutions to any NP-complete problem.

So you *can* solve this reduced form of your original problem, but it is very hard and the time it will take for your program to run will increase exponentially in the length of your list of numbers.

Hope this helps

[centipede]

Hi guys,

Thanks for your replies. Basically we need such a tool because we are looking at invoices (with lots of monetary amounts that almost always include cents - eg. $85.43, $6.02 etc) so in most cases the total can only be made with a specific combination of amounts. And we need to know what items were included in a specific total, in order to make sure that the items included in that total were the right ones. ie. the invoices have 100 numbers that total say $1005.56 and we have say a total for shirts of $351.54 but we don't know which of those hundred numbers go together to make the shirts total of $351.54. So far we have been doing it manually by trial and error (ie. adding numbers trying to get the total) and have been surprisingly successful but I dont think we can do all of them manually.

Anyway - if it's not possible we'll just have to keep trying manually. eek.

centipede.

[Swandog46]

See the Wikipedia article I linked about the subset sum problem. There are two algorithms described in there that (although technically exponentially-slow, that is the time elapsed grows exponentially with the length of the input), will work for sufficiently small inputs. One is divide-and-conquer and the other is dynamic programming. If you want to write a program, that's the way to do it..... (it boils down to a sophisticated way of doing the guess-and-check you were already doing by hand).