Choose cells that come closest to adding up to a certain total

melodramatic

Board Regular
Joined
Apr 28, 2003
Messages
187
Office Version
  1. 365
Platform
  1. Windows
This is probably the strangest query I've put before you, and I think it's probably a dud. But, I'm hoping that someone can prove me wrong.

I am in charge of our daily lunch here at work, and break that lunch down on my credit card according to how many people from our two buildings (A&D) were on the lunch list. Accordingly, I charge out per the average meal cost against the number per building.

All has worked well since I took on this task a year ago. UNTIL, I.T. let some wonder-consultant change out all of our accounting software. I am no longer able to go into each charge and split it to different accounts - every single charge can go to only one charge code now. So much for splitting.

Luckily, I do my charge-outs only once a month (and that day is coming up on Wednesday, when May ends). What I'm planning on doing is taking the total of the charges for the month (using the April figures here, that was $1,425.10 for Bldg A, and $2,710.06 for Bldg D), and pulling receipts that match closest to that amount. Yes, the shortcut system that we now have in accounting takes us all 4x the amount of time to do accounting work.

Sorry, I digress in my frustration.

So, is there a way that I can tell Excel - "hey - if you look at the "A Charge" column in the table, (starting at Row 3, you're in a table), find me the receipts that will bring me the closest to $1,425.10?

Thanks in advance for looking at this!

$4,135.16$1,425.10$2,710.06
04-22AD
DateVendorType Meal# MealsA #D #ChargeA ChargeD Charge
04/04/22 (Mon)ZaxbysChicken21714$200.88
$66.96​
$133.92​
04/06/22 (Wed)Romeros Las BrazasMexican18612$275.84
$91.95​
$183.89​
04/07/22 (Thu)First Class BBQBBQ21615$255.60
$73.03​
$182.57​
04/08/22 (Fri)Every BelliesPotatoes & Burgers19712$267.11
$98.41​
$168.70​
04/11/22 (Mon)Chick-fil-AChicken Sandwiches, Wraps & Salads16511$187.06
$58.46​
$128.60​
04/12/22 (Tue)SchlotzskysSandwiches19712$250.04
$92.12​
$157.92​
04/13/22 (Wed)Joes Italian GrillItalian23914$319.09
$124.86​
$194.23​
04/14/22 (Thu)French QuarterCajun20713$325.41
$113.89​
$211.52​
04/18/22 (Mon)Backyard GrillAmerican (w/seafood)16313$224.46
$42.09​
$182.37​
04/19/22 (Tue)McAlisters DeliSandwiches19613$226.50
$71.53​
$154.97​
04/20/22 (Wed)Yangs KitchenChinese271116$281.71
$114.77​
$166.94​
04/21/22 (Thu)Classic Events CafeBurgers, etc.20614$256.29
$76.89​
$179.40​
04/22/22 (Fri)SmashburgerBurgers, etc.17611$222.94
$78.68​
$144.26​
04/25/22 (Mon)ZaxbysChicken261412$260.39
$140.21​
$120.18​
04/26/22 (Tue)Jersey MikesSandwiches21417
$0.00​
$0.00​
04/27/22 (Wed)Romeros Las BrazasMexican24816$353.41
$117.80​
$235.61​
04/28/22 (Thu)First Class BBQBBQ18513$228.43
$63.45​
$164.98​
04/29/22 (Fri)Every BelliesPotatoes & Burgers20614
$0.00​
$0.00​
 
Hi @Xlambda, I would be very interested in seeing any alternative approaches. I've encountered several problems of this type--involving sums of partitions--with variations regarding the optimization objective: sometimes to minimize the difference between the target sum and the partition sum, other times to obtain the target sum with the fewest elements in the partition. I'll check out ARRANGEMENTS, and if you don't mine--just in case I miss a development there--if you develop something that might offer an alternative solution for @melodramatic to consider, would you mind posting back here with a link to the specific ARRANGEMENTS post? I appreciate your interest in this and thanks for looking into it further.
 
Upvote 0

Excel Facts

Format cells as currency
Select range and press Ctrl+Shift+4 to format cells as currency. (Shift 4 is the $ sign).
I appreciate your interest in this and thanks for looking into it further.
Yes Sir, Thank you Sir! I will prepare the presentation and I will place a link here also. ✌️🙏
 
Upvote 0
Xlambda - I apologize for the long delay in answering - but D365 has been killing me, and I've not had time to look at anything.

I absolutely invite you to post under your thread, and will definitely go to look at it. However, I think this has hit the point that I've given up on the macro idea. Instead, what I've done is created a toggle, where I have a column where the actual charges are added, and then another column where charges add up according to whether I toggle the charge to go to A or D. At the top, a box tells me how close I am to the actual charge, and I just play with the numbers. For my July charges, I had about 90 charges, and actually was able to toggle the charges until I got them to $3.69 of the actual.

Meanwhile, thank you to everyone who tried to help me through this!
 
Upvote 0
Xlambda - I apologize for the long delay in answering - but D365 has been killing me, and I've not had time to look at anything.

I absolutely invite you to post under your thread, and will definitely go to look at it. However, I think this has hit the point that I've given up on the macro idea. Instead, what I've done is created a toggle, where I have a column where the actual charges are added, and then another column where charges add up according to whether I toggle the charge to go to A or D. At the top, a box tells me how close I am to the actual charge, and I just play with the numbers. For my July charges, I had about 90 charges, and actually was able to toggle the charges until I got them to $3.69 of the actual.

Meanwhile, thank you to everyone who tried to help me through this!
No problem at all, take all the time you need. If you can provide more data I will consider finding other ways of approaching a solution, not only with ARRANGEMENTS posts #34 - #38
 
Upvote 0
@melodramatic, I'm curious if you've tried the macro I posted previously. There were several variants, so to eliminate any potential confusion, I'll repost what I believe might be the easiest to implement. I've added a backend analysis utility to this version so that the most preferred combination (of those returned by the code) is automatically identified and used to produce the final results.

In the file available at the link below there is a [Source] worksheet on which you will find an input table that is set up to accept input that closely resembles your initial post. Ideally this input table or your source table will be adjusted so that their structures are identical, in which case Step 1 below will be straightforward. To obtain the solution, follow these six steps (references refer to those on sheet [Source] unless otherwise noted):
  1. Copy monthly data and paste into cells F6:K6 and down. If data contain formulas, use Paste Special > Values instead.
  2. Review column L and ensure that a 1 appears for each item to consider in the analysis. Generally, line items having a Charge=0 should not be considered in the analysis, so the 1 would be deleted on that row in column L. Ensure any other rows to avoid also have a blank in column L.
  3. Formulas in the table compute the weighted sums of Building A and Building D charges (M6:N6 and down). Copy the ideal weighted sum for Bldg A in cell M4 and Paste Special > Value into cell C2.
  4. Formulas prepare the input data set for the VBA code. Copy Q6:R6 and down and Paste Special > Values into A2:B2 and down. Delete anything below the new pasted information in columns A:B.
  5. Run the VBA code: Developer>Macros>Control3.
  6. Results are returned to the [Results] worksheet. A backend analysis utility is in columns V:Y. Of all results returned to the [Results] sheets, only those whose sum is within some tolerance zone of the target are brought forward onto this worksheet. Adjust the tolerance in cell V1 to reduce or expand the number of results carried onto this sheet. Formulas then identify the first best set of KeyCodes whose sum is closest to the Target and the results appear in the blue results table S5:T5 and down.
There are a few copy/paste special operations, but the entire process should only take a minute or so to generate the answer. You may need to activate the Developer tab so that you can run the VBA code. The code is included and ready to run in the workbook. Please post back if you have any questions or encounter any issues.
 
Upvote 0
Xlambda - I apologize for the long delay in answering - but D365 has been killing me, and I've not had time to look at anything.

I absolutely invite you to post under your thread, and will definitely go to look at it. However, I think this has hit the point that I've given up on the macro idea. Instead, what I've done is created a toggle, where I have a column where the actual charges are added, and then another column where charges add up according to whether I toggle the charge to go to A or D. At the top, a box tells me how close I am to the actual charge, and I just play with the numbers. For my July charges, I had about 90 charges, and actually was able to toggle the charges until I got them to $3.69 of the actual.

Meanwhile, thank you to everyone who tried to help me through this!
Problem recap: We have an array of values "a" and we need to find a group of them, that has "gr" elements that summed up will be as close as possible to a target value "tg".
I think your problem has a much more simpler solution, since your acceptable margin of error is quite large (3.98 is huge)
If you have like 90-100 charges/month, combinatorics accurate approach is too much for excel in many ways.
If the grouping array has let's say gr=40 elements (less than half of tot charges/month), total combinations w/o repetitions (since we need the sum, order is not important) will be:
=COMBIN(90,40) =5.98709086469727E+25
If excel needs 1E-20 sec for each calculation total calc time will be:
=5.98709086469727E+25*1E-20/60/60/24 =6.9 days
Instead of calculating all possible combinations we can generate a consistent nr. of random index distributions "ni" (without repetitions) of "gr" elements each and calculate the error margin for the sum of each of them, choosing one with the smallest margin to the target "tg" and displaying the results.
RSGT(a,tg,[ni],[ng]) Random Sum Group Target
a: array of charges
tg: target value
[ni]: nr. of iterations (nr. of random index distributions)
- if omitted ni=10000, or, for greater chances of smaller error margins we can use 30000 or more, calc time for 10000 aprox 1 sec
[gr]: grouping nr. of elements
- if omitted, gr will be estimated gr=int(tg/average(a)), otherwise we can introduce a dif value
Excel Formula:
=LAMBDA(a, tg, [ni], [gr],
    LET(
        r, ROWS(a),
        g, IF(gr, gr, INT(tg / AVERAGE(a))),
        n, IF(ni, ni, 10000),
        ia, LAMBDA(INDEX(SORTBY(SEQUENCE(r), RANDARRAY(r)), SEQUENCE(g))),
        m, MAP(
            SEQUENCE(n),
            LAMBDA(x,
                LET(
                    y, SORT(ia()),
                    z, INDEX(a, y),
                    s, ABS(SUM(z) - tg),
                    TEXTJOIN(",", , s, y)
                )
            )
        ),
        f, INDEX(SORT(m), 1, 1),
        x, --TEXTSPLIT(f, , ","),
        y, INDEX(a, DROP(x, 1)),
        HSTACK(x, VSTACK("val", y))
    )
)
Random SUM grouping target.xlsx
ABCDEFGHIJKLMNOPQRSTU
1a: random generated with formula =ROUND(RANDARRAY(100,,1,100),2) 100 values btwn 1 min and 100 max
2spin?
3n <= if "y" function recalculates, if "n" freezeshelper column for CF of "a"
4atarget "tg"=IFNA(XMATCH(SEQUENCE(ROWS(B5:B104)),F7:F45),0)
542.821735.24=IF(F3="y",RSGT(B5:B104,D5),F6#) <= formula to prevent RSGT to recalculate0
610.980.01val0
718.9689.71result array elements0
815.45766.85 - top left cell, smallest error margin of all index distributions0
962.13sum "a"923.94 - 1st column, indexes values ascending order that correspond to smalles error margin0
1089.715102.71077.74 - 2nd column, values extraction of "a" correspondent to matching indexes1
1166.851256.122
1298.51default gr estimation2687.320
1323.94=INT(D5/AVERAGE(B5:B104))2795.25check gr3
1477.74343282.35=ROWS(F6#)-14
1586.173484.61340
1656.123612.645
179.34111.87check error margin0
1813.31431.93=ABS(SUM(INDEX(F6#,,2))-D5)0
194.544443.310.010
2095.044680.280
2138.294815.840
2218.034929.150
2368.265233.030
2430.445656.990
2588.255780.320
2693.85912.890
2797.846291.980
2895.586723.690
291.096868.820
3087.327137.026
3195.257428.217
3221.597578.540
3356.767653.950
3499.787758.920
3562.557964.750
3682.358117.298
3731.848519.870
3884.618652.369
3973.519433.520
4012.649864.1710
4132.280
4264.930
4380.050
4438.460
4511.8711
462.780
471.9312
4843.3113
4924.470
5080.2814
5169.870
5215.8415
5329.1516
5428.550
5535.020
5633.0317
5718.020
5850.270
5962.520
6056.9918
6180.3219
6294.050
6312.8920
6446.880
657.960
6691.9821
6769.520
6871.290
6949.970
7029.320
7123.6922
7268.8223
7388.330
7475.940
7537.0224
7638.970
7755.450
7828.2125
7978.5426
8053.9527
8158.9228
8255.860
8364.7529
8489.550
8517.2930
861.340
8781.080
8826.850
8919.8731
9052.3632
9135.090
9211.090
9362.620
9487.170
9547.520
9667.260
9738.720
9833.5233
9957.750
10068.420
10182.050
10264.1734
1037.710
10477.730
105
Sheet1
Cell Formulas
RangeFormula
Q4,I18,I14,D13,F5Q4=FORMULATEXT(Q5)
Q5:Q104Q5=IFNA(XMATCH(SEQUENCE(ROWS(B5:B104)),F7:F45),0)
F6:G40F6=IF(F3="y",RSGT(B5:B104,D5),F6#)
D10D10=SUM(B5:B104)
D14D14=INT(D5/AVERAGE(B5:B104))
I15I15=ROWS(F6#)-1
I19I19=ABS(SUM(INDEX(F6#,,2))-D5)
Dynamic array formulas.
Cells with Conditional Formatting
CellConditionCell FormatStop If True
B5:B104Expression=Q5textNO
F6:G106Expression=--F6<>0textNO
 
Upvote 0
To reveal how simple the concept and the function is, will unfold RSGT functionality in 2 parts, step by step.
Part 1, about initial variables and index array embedded lambda ia()
r,g,n variables quite straight forward
r, ROWS(a)
g, IF(gr, gr, INT(tg / AVERAGE(a)))
if gr omitted g=int(tg/average(a)), if not assigns input value
n, IF(ni, ni, 10000) if ni omitted n=10000 , if not assigns input value
ia, LAMBDA(INDEX(SORTBY(SEQUENCE(r), RANDARRAY(r)), SEQUENCE(g)))
- ia(), embedded lambda function, argument free function, creates a single random distribution (no duplicates) of "g" elements of index nr. btw 1 and rows(a)
Random SUM grouping target.xlsx
ABCDEFGHIJKLMNO
1
2ia() functionalityexample for r=20, g=12
3
4r,20random sortingg,12
5array indexesno dupsextracting only g=12 group elements
6=SEQUENCE(20)=RANDARRAY(20)=SORTBY(B7#,D7#)=INDEX(F7#,SEQUENCE(12))
710.35882144
820.3385731919checking no dups
930.7895281515=ROWS(UNIQUE(H7#))=12
1040.0646481818TRUE
1150.704751717
1260.54577422
1370.93309411
1480.4392531212
1590.5187121313
16100.6398188
17110.8316322020
18120.40173699
19130.404216
20140.71447510calling ia() for r=20, g=12
21150.0958645=LAMBDA(INDEX(SORTBY(SEQUENCE(20), RANDARRAY(20)), SEQUENCE(12)))()
22160.917692147
23170.30919318
24180.1288291113
25190.0954711615
26200.482232711
2716
285
2910
303
311
3214
3312
34
Sheet2
Cell Formulas
RangeFormula
B6,D6,F6,H6,H21,J9B6=FORMULATEXT(B7)
B7:B26B7=SEQUENCE(20)
D7:D26D7=RANDARRAY(20)
F7:F26F7=SORTBY(B7#,D7#)
H7:H18H7=INDEX(F7#,SEQUENCE(12))
J10J10=ROWS(UNIQUE(H7#))=12
H22:H33H22=LAMBDA(INDEX(SORTBY(SEQUENCE(20), RANDARRAY(20)), SEQUENCE(12)))()
Dynamic array formulas.
 
Upvote 0
Part 2, m variable using MAP, plus final cosmetic calculations.
m,MAP(SEQUENCE(n ),LAMBDA(x,LET(y,SORT(ia()),z,INDEX(a,y),s,ABS(SUM(z)-tg),TEXTJOIN(",",,s,y))))
For each cell contained in MAP array, the lambda helper functions applies same calculations.
Note: for simplicity I have defined ia()=LAMBDA(INDEX(SORTBY(SEQUENCE(20), RANDARRAY(20)), SEQUENCE(12)))
Random SUM grouping target.xlsx
ABCDEFGHIJKLMNOPQRSTUV
1
2for a single cell of array contained in MAP
3target ex:
4630
5asort(ia())"a" index values
683=SORT(ia())=INDEX(B6#,D7#)
772272evaluating error margin
813313=ABS(SUM(F7#)-H4)
96653774
1037664
1164840since MAP can return a single result for each of its cells, we have to textjoin the relevant data
125957 - first value to the left, error margin followed by respective index distribution, ascending order
13401113
14571276=TEXTJOIN(",",,H9,F7#)
1577145174,72,13,37,64,40,57,13,76,51,6,79,48
1613156
17761679 - as we see, for a single random distribution of 12 grouped indexes, error margin is large
18951748 - with MAP we can do this n (ni) times. For n=2000 times, sorting the result and extracting first 10 for visual relevance
1951
206=LET(m,MAP(SEQUENCE(2000),LAMBDA(x,LET(y,SORT(ia()),z,INDEX(B6#,y),s,ABS(SUM(z)-H4),TEXTJOIN(",",,s,y)))),INDEX(SORT(m),SEQUENCE(10)))
21790,1,2,3,4,7,8,10,13,14,16,17,18
22480,1,2,3,7,10,11,12,13,15,16,19,20 - the function extracts only first value (smallest error margin)
2310,1,2,4,5,6,9,10,11,16,17,18,20expanding 1st cellfinal result
24780,1,2,4,7,8,9,12,13,14,15,18,19=--TEXTSPLIT(I21,,",")only indexesindex matching=HSTACK(K25#,VSTACK("val",O26#))
25330,1,3,4,5,6,8,9,10,11,13,15,160 <- err margin=DROP(K25#,1)=INDEX(B6#,M26#)0val
260,2,3,4,6,7,12,13,16,17,18,19,201183183err checking
271,1,2,3,4,6,7,8,11,13,14,16,172272272=ABS(SUM(R26:R37)-H4)
281,1,2,3,4,8,11,13,14,15,16,19,2033133130
291,1,2,3,5,9,10,12,14,15,17,19,204466466
301,1,2,3,8,9,10,12,14,17,18,19,2077575
318840840
321010771077
331313951395
341414511451
351616791679
361717481748
3718181181
38
Sheet3
Cell Formulas
RangeFormula
B6:B25B6=RANDARRAY(20,,1,100,1)
D6,F6,T27,M25,O25,Q24,K24,I20,I14,H8D6=FORMULATEXT(D7)
D7:D18D7=SORT(ia())
F7:F18F7=INDEX(B6#,D7#)
H9H9=ABS(SUM(F7#)-H4)
I15I15=TEXTJOIN(",",,H9,F7#)
I21:I30I21=LET(m,MAP(SEQUENCE(2000),LAMBDA(x,LET(y,SORT(ia()),z,INDEX(B6#,y),s,ABS(SUM(z)-H4),TEXTJOIN(",",,s,y)))),INDEX(SORT(m),SEQUENCE(10)))
K25:K37K25=--TEXTSPLIT(I21,,",")
Q25:R37Q25=HSTACK(K25#,VSTACK("val",O26#))
M26:M37M26=DROP(K25#,1)
O26:O37O26=INDEX(B6#,M26#)
T28T28=ABS(SUM(R26:R37)-H4)
Dynamic array formulas.
 
Upvote 0
Random SUM grouping target.xlsx
ABCDEFGHIJKLMNOPQ
1crazy example 'a' 500 rows, 30000 iterations , error margin =0.0399999999935972a formula: =ROUND(RANDARRAY(500,,1,1000),2)min val 1, max val 1000
2 - time calculation7 sec
3targetall pos combinations1 iter.=1E-100 s
499999.99=COMBIN(500,208)=I5*1E-100/60/60/24/365/1000000
5a9.8738E+1453.13095E+32
6221.54tot calc time in milion years
7936.66=RSGT(B6:B505,E4,30000)fun estimation
87.320.04valestimated
9855.492936.66gr numbercheck error
10662.526289.3=ROWS(D8#)-1=ABS(SUM(E9:E216)-E4)
11289.310117.582080.04
12226.441185.66
1390.6113953.27rows check a
14153.8317905.64=ROWS(B6:B505)
15117.5821540.19500
1685.662213.9
1734.0627639.2
18953.2731328.44
19524.6333501.92
20571.2134886.71
21168.833590.96
22905.6437508.67
23359.8339914.81
24147.2942939.7
25749.265315.15
26540.1954151.83
2713.95743.45
28845.7762289.09
29710.0863533.91
30811.1269648.45
31184.5870825.2
32639.273466.27
33230.5477242.23
3485.778178.47
35176.583894.59
36328.4484361.36
37526.6586502.19
38501.9288644.48
39886.7192306.87
4090.969339.04
41169.2295609.37
42508.6797413.83
43945.3101441.51
44914.81106990.94
45183.37111155.88
46917.8112634.62
47939.7113659.15
48311.8118510.24
49650.31126733.04
5030.61130358.81
51654.53131807.95
52708.24134527.43
53366.54136126.4
54842.26138462.63
55955.81140287.29
56877.26142126.97
57381.2144234.91
5815.15146835.38
59151.83148321.99
60180.11149146.08
Sheet5
Cell Formulas
RangeFormula
A1A1="crazy example 'a' 500 rows, 30000 iterations , error margin ="&D8
I4,G14,G10,I10,D7,L4I4=FORMULATEXT(I5)
I5I5=COMBIN(500,208)
L5L5=I5*1E-100/60/60/24/365/1000000
D8:E216D8=RSGT(B6:B505,E4,30000)
G11G11=ROWS(D8#)-1
I11I11=ABS(SUM(E9:E216)-E4)
G15G15=ROWS(B6:B505)
Dynamic array formulas.
 
Upvote 0

Forum statistics

Threads
1,224,818
Messages
6,181,152
Members
453,021
Latest member
Justyna P

We've detected that you are using an adblocker.

We have a great community of people providing Excel help here, but the hosting costs are enormous. You can help keep this site running by allowing ads on MrExcel.com.
Allow Ads at MrExcel

Which adblocker are you using?

Disable AdBlock

Follow these easy steps to disable AdBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the icon in the browser’s toolbar.
2)Click on the "Pause on this site" option.
Go back

Disable AdBlock Plus

Follow these easy steps to disable AdBlock Plus

1)Click on the icon in the browser’s toolbar.
2)Click on the toggle to disable it for "mrexcel.com".
Go back

Disable uBlock Origin

Follow these easy steps to disable uBlock Origin

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back

Disable uBlock

Follow these easy steps to disable uBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back
Back
Top