Triển khai Python của thuật toán đóng gói

Question

Đối với một ứng dụng tôi đang làm việc trên tôi cần một cái gì đó giống như một thuật toán đóng gói được thực hiện trong Python see here for more details. Ý tưởng cơ bản là tôi có n các đối tượng có kích thước khác nhau mà tôi cần để vừa với các thùng n, trong đó số lượng thùng bị giới hạn và kích thước của cả đối tượng và thùng được cố định. Các đối tượng/thùng có thể là 1d hoặc 2d, thích nhìn thấy cả hai. (Tôi nghĩ rằng các vật thể 3D có thể nhiều hơn mức cần thiết.)

Tôi biết có nhiều thuật toán khác nhau giải quyết vấn đề này, chẳng hạn như Giảm phù hợp nhất và Giảm đầu tiên, nhưng tôi hy vọng có thể có một triển khai trong Python (hoặc PHP/C++/Java, thực sự tôi không phải là cầu kỳ). Bất kỳ ý tưởng?

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)