Implementazioni di Python dell'algoritmo di imballaggio

Question

Per un'applicazione su cui sto lavorando ho bisogno di qualcosa come un algoritmo di imballaggio implementato in Python Vedi qui per maggiori dettagli. L'idea di base è che ho n oggetti di varie dimensioni in cui ho bisogno per adattarmi n Bins, in cui il numero di contenitori è limitato e la dimensione di entrambi gli oggetti e dei contenitori è fissa. Gli oggetti / bidoni possono essere 1D o 2D, interessati a vedere entrambi. (Penso che gli oggetti 3D siano probabilmente più di quello di cui ho bisogno.)

So che ci sono una varietà di algoritmi là fuori che affrontano questo problema, in modo tale che diminuisca e in primo luogo diminuendo, ma speravo che ci potesse essere un'implementazione in Python (o PHP/C ++/Java, in realtà non sono così esigente ). Qualche idea?

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)