Question: Optimizing a set of numbers in a sum

Hi and welcome to the forum.

Is there an upper limit on the amount of values to be considered (currently 43)?

Can you explain your reference to the "total sheet" (which is not in this workbook)?

Regards

If I may ask, how much of this is an Excel specific question and how much is a more generic "algorithm development" question (independent of programming language used)? It looks to me like it is more of a generic algorithm development question.

Do you know what the final answer should be for this data set? If not, do you have a data set that you know the final answer for? If this is a generic algorithm development question, you may need enough data sets where you know what the final answer should be so that you can test any algorithm that is proposed to see if it is robust enough to find the correct answer on several different data sets.

I tried a simple algorithm (detailed below) that gave me 12 possible combinations. Without knowing the final solution, though, I cannot say if this is THE maximum number of combinations or not. We also have only the one data set to test it on.

Algorithm detail:

1) Select maximum value and subtract from desired total (4200-2377=1823).
2) Divide this subtraction by 3 (1823/3=607 2/3) (I wonder if changing the 3 would give more or fewer results?)
3) Lookup a value near step 2 (794)
4) Subtract (1823-794=1029)
5) Lookup a value just larger than step 4 (1050) At this point, I have a large, small, and middle value that add up to just over 4200.
6) Remove these values from the list
7) Go back to 1 with the new list
8) Repeat until the algorithm can not find a new combination that adds up to 4200.

This "works", but I cannot really test if it can find the maximum number of combinations on different data sets or how to know that it has found THE maximum number.

I don't really have an algorithm development background which is why I was trying to see if it was possible to optimize in excel since that's what I use on a day to day basis at work.

I cannot think of any preprogrammed tools in Excel that will do this. I expect that Excel's Solver (after figuring out what to use for an objective function and decision variables and other algorithm development steps) could possibly find a solution for this. I expect there would be a significant amount of effort trying to figure out what OF to use and how to know when you have found THE maximum -- the same kind of problems you will have with developing your own algorithm.

Although your approach is manual,...With regards to a slight bit of automation such that I don't have to manually search for each number in Step 3, I was thinking of creating a conditional formatting IF formula which would highlight the range of numbers that would be close to the new value needed.

I described the approach in steps -- not necessarily manual steps -- but steps that made sense in terms of the available Excel functions that I am familiar with. For example, instead of using "conditional formatting" to highlight values I can manually choose from, I noted that the list is sorted in descending order which makes a simple INDEX(MATCH()) function an obvious choice for looking up and extracting a value from the list. =INDEX(B2:B44,MATCH(608,B2:B44,-1)) [the -1 as the third argument of the MATCH function is what makes it work on descending lists] easily extracts the value just larger than 608. If you are unfamiliar with these or the other lookup and reference functions -- https://support.office.com/en-us/art...__toc309306714

Another thing I do with something like this is make sure to perform all of the calculations in the column immediately below the list. Then, I make sure the result of step 7 ends up in column C adjacent to the starting list. Copy the calculations below column B into column C (pay attention to absolute and relative references as needed to make sure that this copy works out easily), then copy column C and paste 15 or 20 copies to the right.

Here's what I get:

Row\Col	A	B	C	D	E	F	G	H	I
1	Item #	Amount		Item 1	Item 2	Item 3	Sum
2	1	2377		1	20	23	4226		G2: =SUMPRODUCT(($A$2:$A$44 = D2:F2) * $B$2:$B$44)
3	2	2229		2	18	19	4349
4	3	2174		3	16	17	4332
5	4	1832		4	13	15	4427
6	5	1748		5	12	14	4406
7	6	1716		6	10	11	4758
8	7	1695		7	8	9	4898
9	8	1625					0
10	9	1578					0
11	10	1523					0
12	11	1519					0
13	12	1477					0
14	13	1445					0
15	14	1181					0
16	15	1150					0
17	16	1082					0
18	17	1076					0
19	18	1070					0
20	19	1050					0
21	20	996					0
22	21	874					0
23	22	867					0
24	23	853					0
25	24	794					0
26	25	561					0
27	26	557					0
28	27	513					0
29	28	477					0
30	29	475					0
31	30	437					0
32	31	390					0
33	32	382					0
34	33	380					0
35	34	375					0
36	35	370					0
37	36	370					0
38	37	369					0
39	38	359					0
40	39	354					0
41	40	351					0
42	41	344					0
43	42	343					0
44	43	335					0

Sub TD()
  Const dMin        As Double = 4200#
  Dim avdInp        As Variant
  Dim aviOut        As Variant

  Dim i             As Long
  Dim j             As Long
  Dim k             As Long

  Dim nInp          As Long
  Dim nOut          As Long

  With Range("B2", Cells(Rows.Count, "B").End(xlUp))
    .Sort Key1:=.Cells(1), Order1:=xlDescending, Header:=xlNo
    avdInp = .Value2
  End With
  nInp = UBound(avdInp, 1)
  ReDim aviOut(1 To nInp \ 3, 1 To 3)

  For i = 1 To nInp
    For j = nInp - 1 To i + 1 Step -1
      For k = nInp To j + 1 Step -1
        If avdInp(i, 1) + avdInp(j, 1) + avdInp(k, 1) >= dMin Then
          nOut = nOut + 1

          aviOut(nOut, 1) = i
          aviOut(nOut, 2) = j
          aviOut(nOut, 3) = k

          avdInp(j, 1) = -1E+300
          avdInp(k, 1) = -1E+300

          GoTo Nexti
        End If
      Next k
    Next j
Nexti:
  Next i

  With Range("D2").Resize(nInp \ 3, 3)
    .ClearContents
    .Value = aviOut
  End With
End Sub

WTY, Alf

It would be easy enough to generalize for more items in each combination.

Right now, it's hard-coded for three items (the three concentric loops); it picks the largest value, then looks for the smallest combination of two other items that meets or exceeds the required total.

Generalized code would do about the same thing: pick the largest number remaining and generate combinations of the others from small to large, but without using concentric loops.