Variation of Knapsack in Excel

Question

So, I need to find the total number of combinations for a list of 10 data points that add up to AT LEAST 100. All of the examples to solve this I've found only give the number of combinations that EQUAL a number. How can I total the combinations that are higher than 100? Is this doable without VBA in Excel?

Another idea was calculating the total number of combinations (10!) and subtracting those UNDER 1,000 to find the number. But again, how to find the total number of combinations falling in a range?

Problem statement: 10 data points (65, 52, 48, 44, 42, 41, 39, 38, 30, 18) How many combinations can total at least 100?

Sources I've tried (I can't post more than 2 links) http://www.tushar-mehta.com/excel/templates/match_values/index.html

Find out which combinations of numbers in a set add up to a given total

*"calculating the total number of combinations (10!)"* ... The number of possible subsets is actually `2^n`, not `n!`. — A.S.H, Jun 13 '17 at 15:19

Gary's Student · Answer 1 · 2017-06-15T01:08:58.647

3

Enter the 10 items in A1 through J1
In K1 enter the formula =IF(ROW()<512,"0" & DEC2BIN(ROW(),9),"1" & DEC2BIN(ROW()-512,9))
Copy row 1 down through row 1023
Copy column K and PasteSpecialValues into column L
Use TextToColumns to parse column L into columns M through V
In W1 enter =SUMPRODUCT((A1:J1)*(M1:V1)) and copy down

Column W contains the sums of all possible combinations.

Finally, in another cell, enter:

=COUNTIF(W:W,">=" & 100)

EDIT#1:

To generate a 36 bit binary pattern, I use:

=DEC2BIN(INT(ROW()/2^27),9)&DEC2BIN(INT(MOD(ROW(),2^27)/2^18),9)&DEC2BIN(INT(MOD(ROW(),2^18)/2^9),9)&DEC2BIN(MOD(ROW(),2^9),9)

So for 20 bits, just use:

=RIGHT(DEC2BIN(INT(ROW()/2^27),9)&DEC2BIN(INT(MOD(ROW(),2^27)/2^18),9)&DEC2BIN(INT(MOD(ROW(),2^18)/2^9),9)&DEC2BIN(MOD(ROW(),2^9),9),20)

EDIT#2:

To do something like TextToColumns with VBA, select the cells and run this macro:

Sub PseudoTextToColumns()
    Dim r As Range, L As Long, i As Long, t As String
    For Each r In Selection
        t = r.Text
        L = Len(t)
        For i = 1 To L
            r.Offset(0, i).Value = Mid(t, i, 1)
        Next i
    Next r
End Sub

NOTE:

This will not work for 21 items.

edited Jun 15 '17 at 01:08

answered Jun 13 '17 at 15:55

Gary's Student

95,722
10
59
99

1

Nice (+1) Excel 2013 has a `BITAND` function that could be used to get the bits without quite so much fuss (I think -- I'm still stuck with Excel 2010 so can't test it) – John Coleman Jun 13 '17 at 16:11
Nice, +1 too!. I changed my routine below to be a UDF, so that it would be curious to try it with a formula in `X1`: `=CombinationsByBruteForce(A1:J1, 100)`... It should yield the same result ;) – A.S.H Jun 13 '17 at 16:47
Notice it is still a brute force approach, kind of doing the same thing in VBA or using Excel formulas: examining all possible combinations. – A.S.H Jun 13 '17 at 16:54
@A.S.H I agree completely – Gary's Student Jun 13 '17 at 17:14
anyway to do this in Solver to give same result? – Joe Johnson Jun 13 '17 at 18:09
@Gary'sStudent the next part of the problem asks to do this same thing with 20 data points. It looks like this method won't work with so many? – Joe Johnson Jun 13 '17 at 18:27
@JoeJohnson You would need to modify the column **K** formula to generate 20 bits, etc. – Gary's Student Jun 13 '17 at 18:36
@Gary'sStudent what is the VBA code for this text2columns macro? – Joe Johnson Jun 13 '17 at 18:45
@Gary'sStudent here is what i modified it to, but i get the #NUM! error – Joe Johnson Jun 13 '17 at 18:46
@Gary'sStudent =IF(ROW()<524288,"0" & DEC2BIN(ROW(),19),"1" & DEC2BIN(ROW()-524288,19)) – Joe Johnson Jun 13 '17 at 18:47
@JoeJohnson See my **EDIT#1** – Gary's Student Jun 13 '17 at 19:01
thanks @Gary'sStudent - last thing, can you share the code for the VBA Macro to do the textToColumns? – Joe Johnson Jun 13 '17 at 19:38
@JoeJohnson See mt **EDIT#2** – Gary's Student Jun 13 '17 at 20:05

A.S.H · Answer 2 · 2017-06-13T16:45:30.277

VBA Brute Force solution

I would share the following brute force solution that checks all possible combinations. It is fast enough on small arrays up to 15 entries or so. It solves your problem and you can take it as a model for any brute computation and also as a starting point to optimize and apply faster algorithms. It can also be a good basis for testing any optimized algorithm that you might implement later.

Option Explicit

' Main function. Computes the all combinations and prints those that exceed the target
' Each combination is specified by a mask of bits that specifies whether to take o to leave the entry
Function CombinationsByBruteForce(inputArray() As Double, target As Double) As Long
  Dim mask As Long, count As Long
  For mask = 1 To 2 ^ (1 + UBound(inputArray)) - 1
    If SumByMask(inputArray, mask) > target Then
      count = count + 1
      PrintByMask inputArray, mask
    End If
  Next
  Debug.Print "Total number of successful combinations: " & count
  CombinationsByBruteForce = count
End Function

' computes the sum for a given combination.  The combination is specified by a mask of bits
' that tells which entries belong to the combination (the 1 bits)
Function SumByMask(inputArray() As Double, mask As Long) As Double
  Dim bit As Long
  For bit = 0 To UBound(inputArray)
    If (mask And (2 ^ bit)) <> 0 Then SumByMask = SumByMask + inputArray(bit)
  Next
End Function

' Prints out the entries belonging to a combination specified by a mask
Sub PrintByMask(inputArray() As Double, mask As Long)
  Dim bit As Long
  For bit = 0 To UBound(inputArray)
    If (mask And (2 ^ bit)) <> 0 Then Debug.Print inputArray(bit),
  Next
  Debug.Print
End Sub

' For testing. An array of doubles and a target are specified.
' The variant array is copied into a Double array to improve speed
Sub testing()
  Dim target As Double: target = 350   ' target number to exceed
  Dim test: test = Array(65, 52, 48, 44, 42, 41, 39, 38, 30, 18)

  'convert to explicit array of Double
  ReDim inputArray(UBound(test)) As Double
  Dim i As Long
  For i = LBound(test) To UBound(test): inputArray(i) = test(i): Next

  ' Launsh the brute force computation
  CombinationsByBruteForce inputArray, target
End Sub

Output for the above test:

 65          52  48          44   42          41  39          38  
 65          52  48          44   42          41  39          30  
 65          52  48          44   42          41  38          30  
 65          52  48          44   42          39  38          30  
 65          52  48          44   41          39  38          30  
 65          52  48          42   41          39  38          30  
 65          52  44          42   41          39  38          30  
 65          52  48          44   42          41  39          38   30         
 65          52  48          44   42          41  39          38   18         
 65          52  48          44   42          41  39          30   18         
 65          52  48          44   42          41  38          30   18         
 65          52  48          44   42          39  38          30   18         
 65          52  48          44   41          39  38          30   18         
 65          52  48          42   41          39  38          30   18         
 65          52  44          42   41          39  38          30   18         
 65          48  44          42   41          39  38          30   18         
 52          48  44          42   41          39  38          30   18         
 65          52  48          44   42          41  39          38   30          18  
Total number of successful combinations: 18

As an entry point for solving with the solver, you can try a BIP model, where the decision variables are the bits of the mask. The solver should then apply some branch and bound or similar technique to find a combination. But to print out all the successful combinations with the solver seems much more difficult to solve with the solver, because it is not an optimization problem.

Variation of Knapsack in Excel

2 Answers2