Python 打包算法的实现

Question

我正在开发一个应用程序，需要在Python中实现一种类似打包算法的东西，详细信息可以查看这里。基本的想法是，我有n个不同大小的物品，需要把它们放进n个箱子里，而箱子的数量是有限的，物品和箱子的大小都是固定的。这些物品和箱子可以是一维的，也可以是二维的，我对这两种都感兴趣。（我觉得三维物品可能对我来说有点多。）

我知道有很多算法可以解决这个问题，比如最佳适应递减法和首次适应递减法，但我希望能找到一个用Python实现的版本（或者PHP/C++/Java，实际上我并不太挑剔）。有没有什么好的建议？

Answer 1

这是一个链接，指向一个名为“BinPacking.py”的Python代码文件。你可以通过这个链接查看具体的代码内容。

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