VBA programming - Recursiveness, boolean backpack

Asked

Viewed 175 times

0

I have a similar situation to boolean backpack. I have a table with N lines. Column 'A' contains a length (m²), column 'B' contains a price (R$).

I need to get all possible sums from column 'A' up to a certain value in meters (x) and, the best combination of meter sum and value should be shown so that in meters it does not exceed the value 'x' that is stipulated.

In researches, I got a code that at first would solve the problem but I have gotten several errors, as for example, the variable 'Me' (never heard).

Just follow the code. I would like help to resolve the issue.

Option Explicit
'retirado comando private
Sub cmbBerechnen_Click()
   Dim dblZielwert   As Double
   Dim dblToleranz   As Double
   Dim adblBeträge() As Double
   Dim varResult     As Variant
   Dim m             As Long
   Dim n             As Long
   Dim gblnStop      As Boolean
   
   gblnStop = False
   
   With Me
      dblZielwert = .Range("B2")
      dblToleranz = .Range("C2")
      .Range("D2:IV65536").ClearContents
      ReDim adblBeträge(1 To 100)
      For m = 2 To 101
         If (.Cells(m, 1) <> "") And (IsNumeric(.Cells(m, 1))) Then
            adblBeträge(m - 1) = .Cells(m, 1)
         Else
            ReDim Preserve adblBeträge(1 To m - 1)
            Exit For
         End If
      Next
      ReDim Preserve adblBeträge(1 To UBound(adblBeträge) - 1)
      
      MsgBox "Found Solutions : " & Kombinations(adblBeträge, dblZielwert, Me, 4, 2, dblToleranz)
      
      Application.StatusBar = False
   End With
Call CompileOutput
End Sub
Private Sub cmdAbbrechen_Click()
   gblnStop = True
End Sub
Option Explicit
' Set to "True" for Stop
Public gblnStop As Boolean
Public Function Kombinations(SourceNumbers As Variant, Target As Double, DestSheet As Worksheet, _
   DestCol As Long, DestRow As Long, Optional Tolerance As Double, Optional Previously As Variant, _
   Optional ActLevel As Long, Optional ActFound As Long) As Long
   
   Dim i As Long
   Dim k As Long
   Dim dblCompare As Double
   Dim dblDummy As Double
   Dim varDummy As Variant
   
   ' Do Other events (prevents for freeze)
   DoEvents
   
   ' Global Variable to Stop when is set True
   If gblnStop = True Then Exit Function
   If Not IsMissing(Previously) Then
      
      ' Calculate Sum
      For Each varDummy In Previously
         dblCompare = dblCompare + varDummy
      Next
      
   Else
      ' First time call
   
      ' Sort source by size
      For i = 1 To UBound(SourceNumbers)
          For k = i + 1 To UBound(SourceNumbers)
              If SourceNumbers(k) < SourceNumbers(i) Then
                  dblDummy = SourceNumbers(i)
                  SourceNumbers(i) = SourceNumbers(k)
                  SourceNumbers(k) = dblDummy
              End If
          Next
      Next
      
      ' Make new collection
      Set Previously = New Collection
      
   End If
   If ActLevel = 0 Then ActLevel = LBound(SourceNumbers)
   For i = ActLevel To UBound(SourceNumbers) ' Test all Numbers
   
      ' Add act Value to Collection
      Previously.Add SourceNumbers(i)
      
      ' Calculate act sum
      dblCompare = dblCompare + SourceNumbers(i)
      
      If Abs(Target - dblCompare) < (0.01 + Tolerance) Then 'trying to set the limit
         
         ' Act sum is in target range
         
         k = DestCol - 1 ' Calculate Destination Column
         
         ActFound = ActFound + 1 ' Count Solutions
         
         With DestSheet
         
            ' Save Solution Array in Worksheet
            For Each varDummy In Previously
            
               k = k + 1
               .Cells(DestRow - 1 + ActFound, k) = varDummy
               
            Next
            
         End With
         
         ' Delete following line, or set finally
         ' Statusbar to "False"
         Application.StatusBar = "Solutions Count : " & ActFound
         
         ' Remove act Value from Collection
         Previously.Remove Previously.Count
      
      ElseIf dblCompare < (Target + 0.01 + Tolerance) Then
      
         ' Act sum is lower then target range
         
         ' Recursive call  the same Function with
         ' higher Level
         Kombinations SourceNumbers, Target, DestSheet, DestCol, DestRow, _
            Tolerance, Previously, i + 1, ActFound
            
         ' Remove act Value from Collection
         Previously.Remove Previously.Count
         
         ' Remove act Value from Sum
         dblCompare = dblCompare - SourceNumbers(i)
      
      Else
   
         ' Act sum is greater then target range
         ' No other Solutions possible in this level
         Previously.Remove Previously.Count
         Exit For
      End If
   Next ' Test with higher Number
   Kombinations = ActFound
End Function

Any idea how to make the code run?

  • me is like a "this" in Vb, which in this case would represent the corresponding excel sheet

  • Me refers to the instance of the Class being used.Read the official reference. Widely used in forms.

  • Possible duplicate of VBA - Backpack problem

  • I believe you have an optimization problem. You can solve this with Operational Research (PO), Linear Programming (PL), Solver. These are some names for the type of modeling to solve the problem. I think you will not need to know all combinations, only the one with the best cost/benefit, this can be obtained with the optimization of the problem.

  • @Thank you for the tip!

  • @danieltakeshi I appreciate the indication of Guilherme’s post but we have a difference in the concepts of problematic. The case I present really seeks the optimal solution of sum. As for Solver, as I explained earlier, it requires the exact sum value. As this case allows the approximate sum of the value 'x', it makes it unproductive to keep testing with the values for Solver to find the sums.

  • In fact, you will use a cost-minimizing objective function (OF) on Solver. And in the constraints of the model (s.t.) create the constraint to search for the nearest value of the desired measure in m². Since it is not exact, programming can become non-linear. It is not a simple modeling, but it is also not otherworldly. Maybe some specialist in the field can explain it better. I know how to use programming only in GLPK, a good reference is: H.P. Williams, "Model Building in Mathematical Programming.

  • It is a problem that only those who have all the data and variables of the problem can analyze. An example how to use.

  • Guys, unfortunately so far I haven’t been able to solve the problem definitively and efficiently. The use of the 'Solver' is a proposal that requires processing time and, when it comes to a large set of items (many lines, in my case +600mil), it is impracticable. Anytime solutions or modifications to the above code appear, or even a new implementation, I am grateful if you share. Thank you.

Show 4 more comments
No answers

Browser other questions tagged

You are not signed in. Login or sign up in order to post.