17
Apr
09

### [VB.Net] Bin Packing

An algorithm for packing a bin with a set of items
Allows for packing in descending order, which in most cases are more efficient

```    Public Class Packing_Bin
Public Number As Integer
Public Size As Integer
Public BinSpace As Integer
Public Items As List(Of Integer)
End Class

Private Sub BinPack(ByVal Items As List(Of Integer), ByVal BinSize As Integer, Optional ByVal DecendingBinPack As Boolean = True)
'Items:
''List of items to pack into the bins
'BinSize:
''Declare the maximum size of the bins
''This is not necessary, you can just state the BinSize when you create a new bin
'DecendingBinPack:
''Sorts the items into decending size order

If DecendingBinPack = True Then
Items.Sort()
Items.Reverse()
End If

''Determine minimum number of bins required
''Again, not necessary, just used to check efficency of algorithm
Dim MinimumBins As Integer
For Each item As Integer In Items
MinimumBins += item
Next
MinimumBins = Math.Ceiling(MinimumBins / BinSize)

''Create initial bin to be packed
Dim Bins As New List(Of Packing_Bin)
Dim InitialBin As New Packing_Bin
With InitialBin
.Number = 1
.Size = BinSize
.BinSpace = BinSize
.Items = New List(Of Integer)
End With

''#Note - If you want to start with x bins with different properties, then create them here too
''Just declare a new Packing_Bin and set the properties

''Loop through out list of items
For Each item As Integer In Items
Dim Allocated As Boolean = False
''Loop through current bins
For i As Integer = 0 To Bins.Count - 1
''If there is space in the bin, add it
If Bins(i).BinSpace >= item Then
Bins(i).BinSpace -= item
Allocated = True
Exit For
End If
Next
''If the item was not added to a bin, create a new bin an add it
If Allocated = False Then
Dim NewBin As New Packing_Bin
With NewBin
.Number = Bins.Count + 1
.Size = BinSize
.BinSpace = BinSize - item
.Items = New List(Of Integer)
End With
''Add the bin to our bin collection
End If
Next

Debug.WriteLine("Minimum Number of Bins Required: " & MinimumBins)
For Each bin As Packing_Bin In Bins
Debug.Write("Bin #" & bin.Number & ": ")
For i As Integer = 0 To bin.Items.Count - 2
Debug.Write(bin.Items(i) & ", ")
Next
Debug.Write(bin.Items(bin.Items.Count - 1) & " - Space Remaining: " & bin.BinSpace & " of " & bin.Size & vbNewLine)
Next
End Sub```

Usage:

```        Dim BinSize As Integer = 15
Dim Items As New List(Of Integer)
Items.AddRange(New Integer() {12, 14, 15, 9, 8, 14, 9, 5, 9, 1, 5, 2, 6, 4, 14, 15, 1, 2, 12, 9})
BinPack(Items, 15, True)```

Would Output:
Minimum Number of Bins Required: 12
Bin #1: 15 – Space Remaining: 0 of 15
Bin #2: 15 – Space Remaining: 0 of 15
Bin #3: 14, 1 – Space Remaining: 0 of 15
Bin #4: 14, 1 – Space Remaining: 0 of 15
Bin #5: 14 – Space Remaining: 1 of 15
Bin #6: 12, 2 – Space Remaining: 1 of 15
Bin #7: 12, 2 – Space Remaining: 1 of 15
Bin #8: 9, 6 – Space Remaining: 0 of 15
Bin #9: 9, 5 – Space Remaining: 1 of 15
Bin #10: 9, 5 – Space Remaining: 1 of 15
Bin #11: 9, 4 – Space Remaining: 2 of 15
Bin #12: 8 – Space Remaining: 7 of 15