# Bin Packing

## Next Fit Algorithm

The basic algorithm is termed the Next Fit Algorithm.  This algorithm starts at the beginning of the Elements array and steps through each one.  Once Bin 1 is full, it moves on and starts placing elements into Bin 2, never looking back to see if an Element in the future may fit inside Bin 1.  This process continues until there are no more Elements.  This is least efficient of the algorithms but it does have a practical benefit.  Think of a conveyor belt placing items in boxes to be shipped to a single customer.  You wouldn't want to have to reverse the conveyor belt to go back to a partially empty box to fit in an item that the customer ordered.
`   Private Sub NextFit()      '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 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)         'If True, move on to next Bin         If BinCount + ElementsCopy(i) > Me.BinHeight Then            'Remove extra, unused Element of this Bin            ReDim Preserve Bins(BinNumber)(BinElement - 1)            'Add another Bin            ReDim Preserve Bins(BinNumber + 1)            BinNumber += 1            'Initialize first element of new bin            ReDim Bins(BinNumber)(0)            BinElement = 0            BinCount = 0         End If         'Place task         Bins(BinNumber)(BinElement) = ElementsCopy(i)         'Keep track of how much is stored in this bin         BinCount += ElementsCopy(i)         'Add Element unless we are done         If i < ElementsCopy.GetUpperBound(0) Then            ReDim Preserve Bins(BinNumber)(BinElement + 1)            BinElement += 1         End If      Next      GC.Collect()   End Sub`

After looking at the code you may be worried about the amount of ReDim Preserve statements.  A better solution would be to make each Bin Array (the array that holds the Elements) as big as the Bin Height right at the declaration and then just chop of the unused (0) elements after the algorithm is done.  An ArrayList could also be used as an alternative.

When the code above executes you will have in your array this structure (using BinHeight = 80, Elements = {26 57 18 8 45 16 22 29 5 11 8 27 54 13 17 21 63 14 16 45 6 32 57 24 18 27 54 35 12 43 36 72 14 28 3 11 46 27 42 59 26 41 15 41 68}):

How to read this graph:  Bin Numbers along the bottom, Bin Height/Amount along the left side, Actual Fill Amount along the top, Individual Element Amount inside of bars.

## You might also like...

### 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 difference between theory and practice is smaller in theory than in practice.”