Forum Discussion
How to find which combination of multiples of a set of 5 numbers will return a given value
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.
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.
- 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.
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]
- 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.
- 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 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.- 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)
- Calculate the sum:
- In a separate cell (B13), enter the following formula:
=SUMPRODUCT(A3:A7, B3:B7)
- In a separate cell (B13), enter the following formula:
- 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:
- 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:
- Go to Developer tab
- Click on Excel Add-ins
- Check Solver Add-in and press OK
- Now go to Data tab, and you will see the Solver in right most pane.
- Create the model:
