打包算法的Python实现

  • Z时代
  • 2024-01-10
  • 分类：问答

对于我正在开发的应用程序，我需要类似以Python实现的打包算法之类的信息，请参见此处以获取更多详细信息。基本思想是，我需要将

n个 大小不同的对象放入 n个

容器中，其中容器的数量是有限的，并且对象和容器的大小都是固定的。对象/容器可以是1d或2d，希望同时看到它们。（我认为3d对象可能超出了我的需求。）

我知道有很多算法可以解决此问题，例如最佳拟合递减和首次拟合递减，但我希望可以在Python（或PHP / C ++ /

Java）中实现，实际上我不是那么挑剔）。有任何想法吗？

回答：

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)

以上是 打包算法的Python实现 的全部内容， 来源链接： utcz.com/qa/400938.html

回到顶部