Bin Packing

First Fit Algorithm

Now let's talk about an algorithm with a little more "intelligence".  The First Fit Algorithm does exactly as its name implies.  It steps through the Elements sticking them into the first Bin it can, if there aren't any Bins that it will fit into, a new Bin is added.  You will get pretty efficient use of Bins with this algorithm.

`   Private Sub FirstFit()      'Checks to make sure everything is initialized      If Elements Is Nothing Then Exit Sub      Dim ElementsCopy(Elements.GetUpperBound(0)) As Integer      ReDim Bins(0)      'Bin Number we are on, Bin Element we are on, Amount placed in the current Bin      Dim BinNumber, BinElement, BinCount As Integer      Dim i, j, k As Integer      'Make a copy of the array incase we need to sort it      DeepCopyArray(Elements, ElementsCopy)      'Sort in descending order if needed      If Me.Decreasing = True Then         Array.Sort(ElementsCopy)         Array.Reverse(ElementsCopy)      End If      'Declare the first element in the first Bin      ReDim Bins(0)(0)      'Loop through each Element and place in a Bin      For i = 0 To ElementsCopy.GetUpperBound(0)         Dim bPlaced As Boolean = False         'Loops through each Bin to find the first available spot         For j = 0 To BinNumber            BinElement = Bins(j).GetUpperBound(0)            'Count the amount placed in this Bin            BinCount = 0            For k = 0 To BinElement               BinCount += Bins(j)(k)            Next            If BinCount + ElementsCopy(i) <= Me.BinHeight Then               'There's room for this Element               ReDim Preserve Bins(j)(BinElement + 1)               Bins(j)(BinElement) = ElementsCopy(i)               bPlaced = True               Exit For            Else               'There's not room for this Element in this Bin            End If         Next         'There wasn't room for the Element in any existing Bin         'Create a new Bin         If bPlaced = False Then            'Add another Bin            ReDim Preserve Bins(BinNumber + 1)            BinNumber += 1            'Initialize first element of new bin            ReDim Bins(BinNumber)(1)            BinElement = 0            Bins(BinNumber)(BinElement) = ElementsCopy(i)         End If      Next      'All Elements have been place, now we go back and remove unused Elements      For i = 0 To BinNumber         For j = 0 To Bins(i).GetUpperBound(0)            If Bins(i)(j) = 0 Then               ReDim Preserve Bins(i)(j - 1)            End If         Next      Next      GC.Collect()   End Sub`

With the same set of data as the last example, this algorithm will lay out something like this in memory:

Comments

Contribute

Why not write for us? Or you could submit an event or a user group in your area. Alternatively just tell us what you think!

Our tools

We've got automatic conversion tools to convert C# to VB.NET, VB.NET to C#. Also you can compress javascript and compress css and generate sql connection strings.

“The most exciting phrase to hear in science, the one that heralds new discoveries, is not 'Eureka!' but 'That's funny...'”