包装算法Python实现 [英] Python Implementations of Packing Algorithm
问题描述
有关我的工作我的应用程序需要像在Python 在这里看到更多详细信息。的基本思路是,我的 N 的不同大小的物体,我需要适应的 N 的回收箱,其中容器的数量是有限的,并且两个对象和箱的尺寸是固定的。这些对象/箱可以是一维或二维,希望看到这两个。 (我认为3D对象可能是比我更需要。)
For an application I'm working on I need something like a packing algorithm implemented in Python see here for more details. The basic idea is that I have n objects of varying sizes that I need to fit into n bins, where the number of bins is limited and the size of both objects and bins is fixed. The objects / bins can be either 1d or 2d, interested in seeing both. (I think 3d objects is probably more than I need.)
我知道有多种算法,在那里,解决这个问题,比如石棉飞度下降,首先适合减少,但我希望有可能是在Python(或者PHP / C ++ / Java的实现,我真的很不是挑剔)。任何想法?
I know there are a variety of algorithms out there that address this problem, such asBest Fit Decreasing and First Fit Decreasing, but I was hoping there might be an implementation in Python (or PHP/C++/Java, really I'm not that picky). Any ideas?
推荐答案
的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实现的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!