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?
""" Partition a list into sublists whose sums don't exceed a maximum using a First Fit Decreasing algorithm. See http://www.ams.org/new-in-math/cover/bins1.html 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.items.append(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 bin.append(item) break else: # item didn't fit into any bin, start a new bin #print 'Making new bin for', item bin = Bin() bin.append(item) bins.append(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 print 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)