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...

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