Implémentations Python de l'algorithme d'empaquetage

Question

Pour une application sur laquelle je travaille, j'ai besoin de quelque chose comme un algorithme d'empaquetage implémenté en Python see here for more details. L'idée de base est que j'ai n objets de différentes tailles que j'ai besoin d'intégrer dans n bins, où le nombre de bacs est limité et la taille des deux objets et des bacs est fixe. Les objets/bacs peuvent être 1d ou 2d, intéressés à voir les deux. (Je pense que les objets 3D sont probablement plus que j'ai besoin.)

Je sais qu'il existe une variété d'algorithmes qui répondent à ce problème, tels que Best Fit Decreasing et First Fit Decreasing, mais j'espérais qu'il pourrait y avoir une implémentation en Python (ou PHP/C++/Java, vraiment je ne suis pas si difficile). Des idées?

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)