Python Implementations of Packing Algorithm


For an application I'm working on I need something like a packing algorithm implemented in Python see here for more details. The basic idea is that I have n objects of varying sizes that I need to fit into n bins, where the number of bins is limited and the size of both objects and bins is fixed. The objects / bins can be either 1d or 2d, interested in seeing both. (I think 3d objects is probably more than I need.)

I know there are a variety of algorithms out there that address this problem, such asBest Fit Decreasing and First Fit Decreasing, but I was hoping there might be an implementation in Python (or PHP/C++/Java, really I'm not that picky). Any ideas?

9/12/2011 6:42:03 PM

Accepted Answer

""" Partition a list into sublists whose sums don't exceed a maximum 
    using a First Fit Decreasing algorithm. See
    for a simple description of the method.

class Bin(object):
    """ Container for items that keeps a running sum """
    def __init__(self):
        self.items = []
        self.sum = 0

    def append(self, item):
        self.sum += item

    def __str__(self):
        """ Printable representation """
        return 'Bin(sum=%d, items=%s)' % (self.sum, str(self.items))

def pack(values, maxValue):
    values = sorted(values, reverse=True)
    bins = []

    for item in values:
        # Try to fit item into a bin
        for bin in bins:
            if bin.sum + item <= maxValue:
                #print 'Adding', item, 'to', bin
            # item didn't fit into any bin, start a new bin
            #print 'Making new bin for', item
            bin = Bin()

    return bins

if __name__ == '__main__':
    import random

    def packAndShow(aList, maxValue):
        """ Pack a list into bins and show the result """
        print 'List with sum', sum(aList), 'requires at least', (sum(aList)+maxValue-1)/maxValue, 'bins'

        bins = pack(aList, maxValue)

        print 'Solution using', len(bins), 'bins:'
        for bin in bins:
            print bin


    aList = [10,9,8,7,6,5,4,3,2,1]
    packAndShow(aList, 11)

    aList = [ random.randint(1, 11) for i in range(100) ]
    packAndShow(aList, 11)
1/13/2013 1:31:09 PM

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow