# Knapsack / Sum-Total Variation. In EXCEL, how to get all combinations of numbers that where the sums fall within a certain range?

Hi I am new here and was hoping one of you could help me.

Note, this topic is similar to some out there, but none have answered this exact question.

It is exactly the same as this unanswered question: https://stackoverflow.com/questions/31248379/vba-to-extract-values-from-a-list-until-the-sum-is-within-a-certain-range

My problem is the following: as an excel user I have a column of numbers, say

5, 6, 7, 8, 8, 9, 14, 17

and what to know all the combinations of sums that fall, for example, within the 25 - 35 range. I will likely only have 4-5 entries/column numbers.

There is one more restriction: I want the combinations to be as small as possible, but still within the range.

so 17 + 9 = 26 is good but 17 + 9 + 5 = 31 is bad (should not be counted) because the group is larger than necessary although it still is within the range.

So overall, I want to get all the possible combinations of numbers in a column that sum to fall within a specific range where the sums are as small as possible, but still within the range.

Hope anyone can help! If not, does anyone know where I might find info to I can learn coding myself :)

Cheers and have a great weekend!!

Place your values in column A and in column B place 0 next to them.

Then in C9 enter the formula:

``````=SUMPRODUCT(A1:A8*B1:B8)
``````

then enter and run this short macro:

``````Sub ABC()
Dim i As Long, s As String
Dim j As Long, K As Long
Dim wf As WorksheetFunction
Set wf = Application.WorksheetFunction

K = 1

For i = 0 To 255
s = wf.Dec2Bin(i, 8)
For j = 1 To 8
Cells(j, 2).Value = Val(Mid(s, j, 1))
Next j
If Range("C9").Value > 24 And Range("C9").Value < 36 Then
For j = 1 To 8
If Cells(j, 2) = 1 Then answer = answer & "," & Cells(j, 1)
Next j
K = K + 1
End If
Next i
End Sub
``````

You will get all 64 solutions listed in column D:

This is based on John Coleman's suggestion.

• Hi! Thank you so much!!! This is tremendously helpful! Do you know if it is possible to somehow get the sum of the numbers in column D? Actually I am working with numbers that are percentages and therefore add up to 100%. so I have 5 entries of 20% each and I want to find the combinations that sum equal to or greater than some threshold say 70%, but also equal to or less than 100%. So it would be awesome if i could link the code to the threshold such that when the threshold updates so do the entries that sum to or surpass that threshold. Again thanks for your fantastic help!!!!!!!!!! – ABC Mar 26 '16 at 17:48
• @ABC You are quite welcome. – Gary's Student Mar 26 '16 at 17:49
• Hi! Thank you so much!!! This is tremendously helpful! Do you know if it is possible to somehow get the sum of the numbers in column D? Actually I am working with numbers that are percentages and therefore add up to 100%. so I have 5 entries of 20% each and I want to find the combinations that sum equal to or greater than some threshold say 70%, but also equal to or less than 100%. So it would be awesome if i could link the code to the threshold such that when the threshold updates so do the entries that sum to or surpass that threshold. Again thanks for your fantastic help!!!!!!!!!! – ABC Mar 26 '16 at 17:54
• Or do you know if it is possible to get an output with the numbers corresponding to the rows in which used entries exist? so for numbers 5 and 6, the output would be 1, 2 – ABC Mar 26 '16 at 17:58
• ok, based on your code I now understand how to incorporate a threshold into the code. – ABC Mar 26 '16 at 18:37

Excel users quite often run into this problem. There is an Excel add-in which makes it easy to find all combinations of numbers that match your criteria called SumMatch

The included picture explains how to set up your criteria to see all the combinations that match them. By modifying the criteria you could get solutions using a free trial of the add-in.