6

I have a number on a spreadsheet which is a combination of many different numbers on a list.

For example:

A list contains: 100, 200, 250, 500, and 1000
The number I need to explain is: 800

The answer would be 500, 200, 100.

I'm dealing with over 1500 currency cells ($xxxx.xx) which make a total (and not all are used, so SUM is useless). I need to understand which numbers were used to create that total (Which isn't a formula, it's a hard-coded number).

THE QUESTION:
Is there a function or VBA that will systematically combine numbers in a given range until it determines which numbers can be added together to make the total?

I want to know before I start writing a brute-force algorithm.

Community
  • 1
  • 1
C-Love511
  • 358
  • 1
  • 7
  • 24
  • 2
    If the numbers were in a *bitwise* pattern (e.g. 1, 2, 4, 8, etc) then it would be comparatively simple. If you are dealing with random currency values there could be more than a single solution. A reiterative VBA loop would be the brute force approach but there are others. see [Find out which combinations of numbers in a set add up to a given total](http://stackoverflow.com/questions/3989807/find-out-which-combinations-of-numbers-in-a-set-add-up-to-a-given-total). –  Jan 26 '15 at 08:34
  • BRILLIANT. This is my exact issue. This helped a ton--I wish I could give you more than 1 upvote. – C-Love511 Jan 26 '15 at 08:38
  • 1
    See also [Combinatorics in excel: Find every possible sum of every possible combination](http://stackoverflow.com/q/26539996/973283) – Tony Dallimore Jan 26 '15 at 10:08
  • 2
    This question isn't asking for a tool or library recommendation. It is very specifically asking if/what built in function does something. This shouldn't have been closed. – RubberDuck Feb 02 '15 at 18:07
  • @RubberDuck I voted to reopen – Chrismas007 Feb 02 '15 at 18:11
  • True, it shouldn't have been closed for that reason, but the "Combinatorics in Excel: Find every possible sum of every possible combination" thread is my exact same question, so this is essentially a duplicate thread. (For the record, I searched a lot on here to find the answer, and that thread never appeared in my results). – C-Love511 Feb 09 '15 at 15:42

4 Answers4

6

You can use SOLVER in excel to get the result.

You can activate it in ADD-INS and it should show up in DATA tab.

You set up your spreadsheet like this:

In one column You have list of numbers You want to check Next column is all zeroes (0) Third column is First*Second (for example 100 * 0) so in the beginning its zero for all rows

Than You add summary of third column and it should also be zero. Example how this data can look like:

100 0   0
200 0   0
500 0   0
50  0   0
60  0   0
80  0   0
120 0   0
90  0   0
TOTAL   0

Now You run solver form data tab and You get interface that You have to feed parameters:

Goal value is the CELL with the sum of all multiplications You are looking for exact value (type in 800)

By changing cels: select range of zeroes in second column

Add thre additional restriction (add button): range of zeroes have to be >= than 0 and <= 1 and int so we only have 0 and 1 as possible results (you have to reselect range every time you add another limitation)

Now press solve and after some time (depending on scale of your data sets ranging from seconds to many minutes) it will change some of the zeroes to 1 indicating which numbers where used to produce Your result.

If there are many possible outcomes it will choose one that he found without indicating that there are more, but running it again may produce different result.

Here is the result I got:

100 1   100
200 0   0
500 1   500
50  0   0
60  0   0
80  1   80
120 1   120
90  0   0
TOTAL   800
Tetlanesh
  • 403
  • 5
  • 9
  • 1
    This was great! By the way, I must have misconfigured something and it kept going on and on. To pause / cancel, press the ESC key and it will take you back to the parameters screen. – John Aug 17 '18 at 14:35
3

Help is on the way.

You can paste this function into a module and adjust it to your needs.

Function GetCombination(CoinsRange As Range, SumCellId As Range) As String
Dim Nb As Integer
Dim Com As String
Dim Sum As Double
Dim r As Range
Set r = CoinsRange
Sum = SumCellId.Value
For Each cell In r.Cells
If Sum / cell.Value >= 1 Then
Com = Com & Int(Sum / cell.Value) & " of " & cell.Value & "  "
Sum = Sum - (Int(Sum / cell.Value)) * cell.Value
End If
Next
GetCombination = Com
End Function

Preconditions:

  1. Coins or bills must be in descending order

My End result: enter image description here

Amen Jlili
  • 1,884
  • 4
  • 28
  • 51
  • Not the question is, should result says that 3 x 500 where used if only one 500 value was in reference data? I got the impression from the OP question that he searches for sum of values he have not multiples of them. I assume even if so its easy to accommodate in your script. – Tetlanesh Jan 26 '15 at 11:40
  • @Tetlanesh: If I understood the OP question, he wants the combination of coins or bills from a predefined list. – Amen Jlili Jan 26 '15 at 11:45
  • If it is coins or bills then sure, however I don't see it mentioned anywhere in question, It would be best if OP shed more light. – Tetlanesh Jan 26 '15 at 12:00
  • Well. You're right. People should explain their questions thoroughly. @Tetlanesh – Amen Jlili Jan 26 '15 at 12:48
  • Yeah, sorry about the confusion--there aren't duplicate values, and no predefined list. For example, it's a list of 1500 different purchases from 2014, in different categories--whoever entered them in QuickBooks did it wrong, so I need to figure out which values go into which accounts. Still, a great starting place, so thank you! – C-Love511 Jan 27 '15 at 16:07
2

Okay, figured out the solution that worked best for me:

First, I found some vba that lets you create infinite strings of binary (rather than the 9 bits Excel has built in). I then used this code to create a UDF for this purpose... Since I was working with chunks of 20-40 "bits", this was absolutely necessary.

Second, I made a counter loop which increased by 1, then changed the binary string to reflect the new number. (1,10,11,100,101,110,111, etc.)

Third, I wrote a formula that breaks the binary string apart, and assigns each 1 or 0 to the corresponding number in the cell next to it. (Just using the LEN(),RIGHT(), and MID() functions to recognize 1s and 0s).

Fourth, I multiplied each value by the 1 or 0 next to it, and then compared the sum of all multiplied numbers to the target value I was looking for.

100% of the time, if given clean data, this finds a solution, if one exists. (Mostly time is a factor though, since this is an exponential function, so the more bits you have, the longer it takes to cycle through them)

This ran at about 3 million combinations in 4 minutes, give or take depending on a few factors

I redid the worksheet, and doubled the speed by having 5 columns, each incremented by one, and having the counter increment by 5 (rather than 1).

C-Love511
  • 358
  • 1
  • 7
  • 24
  • Can you post the code for your solution? It sounds very useful! – ChrisB Mar 29 '17 at 19:15
  • Unfortunately, I left the job that required it in the first place, and it was saved on my personal account there (And I didn't even think to back it up because I never thought about using it elsewhere...I know, stupid.). However, it was incredibly useful, so I'll probably rebuild it and post it up here unless someone beats me to it, or @Patrick finishes his Windows application first. It does run slowly though -- usually I'd be solving a difficult problem comprised of 40-50 possible variables and I'd have to let it run over the weekend. – C-Love511 Jul 12 '17 at 17:41
  • Thanks @C-Love511! – ChrisB Jul 21 '17 at 23:36
  • Deleted the link for the following reasons: 1. I get about 5 requests a day, probably hackers, for people to be editors on the document. You do not need to be an editor to download. 2. It can only handle up to 30 numbers, as the operations get exponentially more expensive with every number, and the people who actually ask tell me that's not enough. 3. It is in desperate need of a rewrite, probably in another language that runs faster. Message if you want it, I'll repost when I get around to remaking it. – C-Love511 Oct 19 '21 at 12:42
1

I've been working on a windows application to do this. I'm close to a solution that I think will satisfy most people's needs.

The number of combinations is the issue for most algorithms, so the key is to ignore as many non-viable combinations as possible.

25 numbers in a list is approx 33 million combinations. 50 numbers in a list is a million millions of combinations. So, doing this in vba is probably not a viable option for most people, and solver won't deal with this very well either.

Brute force doesn't work because there are too many combinations if you're doing a list of more than 2 to 3 dozen numbers.

Patrick
  • 11
  • 1