Macro to find best way to combine numbers to equal a certain sum

Hi all,
I'm pretty good at VBA, but this one is going to be a challenge I think. It'll be interesting for sure. I will have multiple rows and columns of numbers.. Something like this:
7.4 , 7.4 , 7.4 , 7.4 , 7.4 , 7.4
3.9 , 3.9 , 3.9 , 3.9 , 3.9
11.9 , 11.9 , 11.9 , 11.9 , 11.9


It will always be the same number in each column. You can assume it starts an A1. I will adjust as needed. But it could be any number of columns or rows.
I want to enter a number in a cell or be asked by an input box or whatever... (lets say the number 12 but it could be anything up to 40) and have a macro find the best combinations of those numbers to come as close to 12 as possible without going over. It can use any of those numbers in any combination or order or as many as needed to come up with as few of combinations as possible.
So in the example above, 1 possibility would be 11 combinations as follows: (best I can figure in my head quickly lol)
Pair 7.4 with 3.9 five times (sum of 11.3 each pair)
11.9 by itself 5 times
Then one 7.4 left over to be by itself.

Please note that numbers in the same row can be put together.. for example 3.9 could be put together 3 times to equal 11.7 but that's not the best way in this case because it would take 12 combinations to complete instead of 11. So the code can look at all these numbers as not being in any order or arrangement whatsoever.

In case it matters, I want to buy as few 12 foot pieces of steel as possible to cut it and get each of the lengths listed the same number of times as the number of columns it's in. (7.4 feet six times, 3.9 feet five times and 11.9 five times)

Unless Excel has some other way of doing this that I don't know about, it's going to be a challenging macro.

Thank you!
Albert

AliGW,
Ok sorry about that. Thanks!

hrlngrv,
Thank you for this! It looks interesting. I haven't had much time to mess around with it, but I did make a workbook and followed your instructions. The only thing I wasn't sure about was when you said this:
"Then I defined the name SegmentList referring to the formula =Sheet2!$B$5:INDEX(Sheet2!$B$5:$B$1048576,NumSegments)"

I just picked a cell on Sheet2, (F2 actually), put that formula in it and named it SegmentList. That sounds like what you meant. But when I run the code I get Type mismatch error on the 7th line of code.. ie:
numseg = UBound(seglst, 1). I think because it shows seglst as an error 2036 a couple lines above that. I'm attaching the workbook though so if you want to check it and make sure I did everything right you can.
I'm excited about getting this to work and I might be able too if I spent enough time on it, but that's something I don't have much of.. lol
Thank you so much for all the time you have taken to do this. I am impressed to say the least!

If you display the Name Manager dialog, click New to display the New Name dialog, enter the name SegmentList, then in the Refers to box enter the formula

Formula:

Please Login or Register  to view this content.

That defines a name which refers to a dynamic range, that is, a range which automatically resizes as entries are added or deleted in the range named Segments. DO NOT enter this formula in a cell.

hrlngrv,
I got it to work so far. That's pretty cool! I will do some more testing and see how it does but so far with my first couple tests it works perfectly. I'm impressed! Thank you very much!!

hrlngrv

Well upon more testing it works in some cases and others it doesn't. I sure do like it but do you think you could figure out why it doesn't work with some numbers. This is one example of numbers I used that it didn't work with the material length set to 12 on sheet 2:B3
2 2 2 2 2 2 2
5 5 5 5

If I remove 1 of the 2's, it works fine.

This thing is so awesome!... And I'd love it to work all the time!

Originally Posted by achammar

. . . upon more testing it works in some cases and others it doesn't. . . . This is one example of numbers I used that it didn't work with the material length set to 12 on sheet 2:B3
2 2 2 2 2 2 2
5 5 5 5

If I remove 1 of the 2's, it works fine. . . .

Yup, my fault due to inadequate testing. Replace the block

Please Login or Register  to view this content.

with

Please Login or Register  to view this content.

I forgot to add 2 to the current output record's column count.

Note: this block contains the only instance of ReDim Preserve. I'll also add this correction to my original comment.

hrlngrv
That is sooo awesome! What a good job you did here! It works flawlessly as far as I can tell. You have done a very good thing for me! Thank you so very much!!!
I already added to your reputation. I don't know if there's anything else I'm supposed to do here.

hrlngrv1,

I have a quick question. Can I add more rows to the 'Segments' range without having to change anything else? I added columns already awhile back. I think you had it set at 20 columns and I widened it to 42 and it seems to be working fine. If I increase the number of rows from 100 to say 200, will it still work correctly? Thank you again for your genius solution here!

Given the way I defined the names, you should be able to expand the segments range either by including more rows or more columns as long as the total number of segments is fewer than 2^20-4, or 1,048,572. That's because SegmentList is a single column range, beginning below row 1, and Excel only allows for 1,048,576 rows in a worksheet.

Ok that is so awesome! Thanks again!