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

Question

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!!

Answer 1

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
    Dim answer As String
    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
            answer = ""
            For j = 1 To 8
                If Cells(j, 2) = 1 Then answer = answer & "," & Cells(j, 1)
            Next j
            Cells(K, 4) = Mid(answer, 2)
            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.

Answer 2

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.