Python implementation of the packaging algorithm

Question

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

I know that there are many algorithms that address this issue, such as Best Fit Decreasing and First Fit Decreasing, but I was hoping there might be an implementation in Python (or PHP / C ++ / Java, really I am not so picky). Any ideas?

Answer 1

https://bitbucket.org/kent37/python-tutor-samples/src/f657aeba5328/BinPacking.py

""" 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)