Bin Packing

Worst Fit Algorithm

   Despite its name, the Worst Fit Algorithm produces result that are consistently better than the First Fit Algorithm.  This does come with some extra processing though (on small data sets it doesn't really matter).  The only difference between the two algorithms is that Worst Fit picks the Bin with the most amount of free space (or creates a new Bin if no existing one can fit the Element) instead of just picking the first Bin available.

   Private Sub WorstFit()
'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 WorstBin, WorstBinAmount 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)
WorstBin = -1
WorstBinAmount = Me.BinHeight + 1

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

'Find the least full Bin that can hold this Element
If WorstBinAmount > BinCount AndAlso BinCount + ElementsCopy(i) <= Me.BinHeight Then
WorstBinAmount = BinCount
WorstBin = j
End If
Next


If WorstBin = -1 Then
'There wasn't room for the Element in any existing Bin
'Create a new 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)
Else
'There's room for this Element in an existing Bin
'Place Element in "Best Bin"
BinElement = Bins(WorstBin).GetUpperBound(0)
ReDim Preserve Bins(WorstBin)(BinElement + 1)
Bins(WorstBin)(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:


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.

“Linux is only free if your time has no value” - Jamie Zawinski