Implémentations Python de l'algorithme d'emballage
Question
Pour une application sur laquelle je travaille, j'ai besoin de quelque chose comme un algorithme d'empaquetage implémenté en Python voir ici pour plusdétails .L'idée de base est que j'ai n objets de différentes tailles que je dois insérer dans n bacs, où le nombre de bacs est limité et la taille des objets et des bacsc'est réglé.Les objets / bacs peuvent être 1d ou 2d, intéressés à voir les deux.(Je pense que les objets 3D sont probablement plus que ce dont j'ai besoin.)
Je sais qu'il existe une variété d'algorithmes qui résolvent 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 suispas si difficile).Des idées?
La solution
https://bitbucket.org/kent37/python-exemples-tuteur / 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)