包装算法的Python实现

Question

对于我正在处理的应用程序，我需要类似Python see here for more details中实现的打包算法。基本思想是我有n不同尺寸的物体，我需要装入n箱，箱的数量是有限的，物体和箱的尺寸是固定的。物体/箱可以是1d或2d，有兴趣看到两者。 （我认为3D对象可能比我需要的更多。）

我知道有很多算法可以解决这个问题，比如最佳适合度下降和首次适应度下降，但我希望可能会有一个实现在Python中（或者PHP/C++/Java，真的我没那么挑剔）。有任何想法吗？

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)