+ Reply to Thread
Results 1 to 1 of 1

Subset Sum Problem

Hybrid View

  1. #1
    Valued Forum Contributor smuzoen's Avatar
    Join Date
    10-28-2011
    Location
    Brisbane, Australia
    MS-Off Ver
    Excel 2003/2007/2010
    Posts
    610

    Subset Sum Problem

    I had to design a method of filling multiple sets of racks that were of a certain fixed height with individual units called MCC's. Each unit that went within the rack was of different size so aim was to use as few racks as possible and fill the racks optimally given each unit' height - used a recursive function to calculate optimal way of filling the racks while using as few racks as possible. This is a method to calculate a "subset sum problem". I will attach the whole project which draws the units however the main function is what I was interested in - to follow is the recursive function and its method to call.
    Public fR As Boolean
    Function RealEqual(A, B, Optional Epsilon As Double = 0.00000001)
        RealEqual = Abs(A - B) <= Epsilon
        End Function
    Function ExtendRslt(CurrRslt, NewVal, Separator)
        If CurrRslt = "" Then ExtendRslt = NewVal _
        Else ExtendRslt = CurrRslt & Separator & NewVal
        End Function
    Sub recursiveMatch(ByVal MaxSoln As Integer, ByVal TargetVal, InArr(), _
            ByVal HaveRandomNegatives As Boolean, _
            ByVal CurrIdx As Integer, _
            ByVal CurrTotal, ByVal Epsilon As Double, _
            ByRef Rslt(), ByVal CurrRslt As String, ByVal Separator As String)
        Dim I As Integer
        For I = CurrIdx To UBound(InArr, 2)
            If RealEqual(CurrTotal + InArr(2, I), TargetVal, Epsilon) Then
                Rslt(UBound(Rslt)) = (CurrTotal + InArr(2, I)) _
                    & Separator & ExtendRslt(CurrRslt, I, Separator)
                    fR = True
                If MaxSoln = 0 Then
                    If UBound(Rslt) Mod 100 = 0 Then Debug.Print "Rslt(" & UBound(Rslt) & ")=" & Rslt(UBound(Rslt))
                Else
                   ' If UBound(Rslt) >= MaxSoln Then Exit Sub
                   If fR = True Then Exit Sub
                    End If
                ReDim Preserve Rslt(UBound(Rslt) + 1)
           ElseIf IIf(HaveRandomNegatives, False, CurrTotal + InArr(2, I) > TargetVal + Epsilon) Then
            ElseIf CurrIdx < UBound(InArr, 2) Then
                recursiveMatch MaxSoln, TargetVal, InArr(), HaveRandomNegatives, _
                    I + 1, _
                    CurrTotal + InArr(2, I), Epsilon, Rslt(), _
                    ExtendRslt(CurrRslt, I, Separator), _
                    Separator
                If MaxSoln <> 0 Then If fR = True Then Exit Sub
            Else
                'no matches
                End If
            Next I
        End Sub
    Called by
    recursiveMatch MaxSoln, TargetVal, InArr, HaveRandomNegatives, _
            LBound(InArr), 0, 0.00000001, _
            Rslt, "", ", "
    Attached Files Attached Files
    Hope this helps.
    Anthony
    Pack my box with five dozen liquor jugs
    PS: Remember to mark your questions as Solved once you are satisfied. Please rate the answer(s) by selecting the Star in the lower left next to the Triangle. It is appreciated?

+ Reply to Thread

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts

Search Engine Friendly URLs by vBSEO 3.6.0 RC 1