How to find which combination of multiples of a set of 5 numbers will return a given value

[mcinqb3]

Hi all. New to excel, but decent using spreadsheets for trivial things.

Right now, I'm trying to figure out which combinations of a set of 5 numbers or their multiples will give me a sum of AT LEAST a specific value.

For example, the numbers are:

1922

2404

3013

3788

4755

I am trying to combine the smallest number of their multiples that will give me a value of at least 18000.

So,

1922+2404+3013+3788+4755 = 15902 = Doesn't work

1922+4808 (2404*2)+3013+3788+4755 = 18306 = Works

If possible, I'd also like to find the combination that is closest to 18000, but that's not a necessity. I'd also like to find all combinations if that's not a problem, and not just a single instance. And it doesn't need to involve every number in the set, it can also just be 4755 * 4 = 19020.

I know I could do this with brute force and just write down all multiples. but I will be using a similar idea with various groups of numbers and final sums, so I want to just be able to plug and play.

Thanks for any help, and sorry if this isn't clear. Let me know if more information is needed.

[#2]

@mcinqb3 
You can achieve that using the 'Excel Solver', if you're not familiar with it. You can use these steps in order to do that.

1. Create the model:
   • Assuming your set of numbers in A3:A7 (1922, 2404, 3013, 3788, and 4755)
   • Add a blank column to the right of your numbers (Column B)
2. Calculate the sum:
   • In a separate cell (B13), enter the following formula:
     =SUMPRODUCT(A3:A7, B3:B7)
3. Run the Solver:
   • On the Data tab, in the Analysis group, click the Solver button.
   • Configure the Solver Parameters:
     • Set the objective cell to the address of the formula cell (B13).
     • Specify the desired sum value (e.g., 18,000) in the Value Of section.
     • Select the range to be populated with the results (B3:B7) as the By Changing Variable Cells.
     • Add constraints if needed (e.g., binary constraints for whole numbers).
     • here's what it should like:
4. Solve the problem:
   • Click the Solve button.
   • The Solver Results dialog will appear, showing which numbers (or their multiples) contribute to the desired sum.
     
   • Press OK

To make the solver option appear, follow these steps:

1. Go to Developer tab
2. Click on Excel Add-ins
3. Check Solver Add-in and press OK
   
4. Now go to Data tab, and you will see the Solver in right most pane.
   

[#3]

the least number of their multiples will always be = roundup(N/largest option)
the challenge will then be to find the combination that is closest to N but at least that will give you how many terms to use

[#4]

@mcinqb3 

re:

So,

1922+2404+3013+3788+4755 = 15902 = Doesn't work

1922+4808 (2404*2)+3013+3788+4755 = 18306 = Works

I am afraid 18041 also works and closer to 18000

1922+3788+3788+3788+4755=18041

 

18041	41	1922+3788+3788+3788+4755	4755	5	5
18046	46	2404+2404+2404+2404+2404+3013+3013	3013

[#5]

@mcinqb3 

For finding the closest match in the given example, I think we can list all combinations of up to 9 of the values including replacements. For listing combinations I used a lambda function courtesy of @m_tarler . The closest I could find to 18000 with this method was
1922 * 5 + 2404 + 3013 * 2 = 18040

[ref: 'example of counting multi-subsets' section of Combination - Wikipedia article]

[#6]

my impression of what @mcinqb3 needs or wants for this problem is the min number of elements and SECONDLY would be the combination that is closest to the target. Although I don't have time right now I would suggest a do a combination matrix based on a max number of elements determined by ROUNDUP( TARGET / [max element] ). Then filter by those > TARGET and then use the MIN of that (i.e. the closest to the TARGET without being under).
If @mcinqb3 could chime in and say if my assumption is what they want, i would be happy to do it when I have a chance or maybe what was already presented above is what they want.

[#7]

@mcinqb3 

I think Solver is the way to go.

The method is Simplex LP (linear programming).

The integer multipliers x are the optimisation variables.

The objective function is basically the sum of x but I have added a small proportion of the constraint exceedance to act as a tiebreaker.

The main constraint is on g=SUM(a*g) which must exceed the target.

The figure shows the solution returned by Solver.

[#8]

I thought about suggesting the solver but i think I can usually create a function/lambda faster than figuring out how to best implement the Solver. lol. That said, your solver solution is elegant with 1 caveat. I think your 'tie breaker' should be tied to the target (or probably 2x target) to make sure in a more general solution, that tie breaker doesn't become > that primary criteria (sum of X). I think dividing by 2x target will guarentee it as I don't think dividing by target alone will guarentee it.