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
        Bins.Add(InitialBin)

        ''#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).Items.Add(item)
                    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)
                    .Items.Add(item)
                End With
                ''Add the bin to our bin collection
                Bins.Add(NewBin)
            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

Advertisements

0 Responses to “[VB.Net] Bin Packing”



  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: