1

我正在尝试为 bin-packing 编写最适合的算法。装箱问题：在给定体积容量的情况下，最小化用于包装物品的箱的数量。

这个启发式应该做的是

  1. 尝试将物品放在可以容纳它的最满的垃圾箱中，即留下最少空间的垃圾箱

  2. 如果没有找到 bin，则启动一个新 bin。

为了写这个，我做了一个辅助卷。对于您要放置的项目，将卷添加到每个 bin。容量最大的垃圾箱（仍然可行）将获得该项目。我在 Python 中尝试了以下操作：

item = ['a', 'b', 'c', 'd', 'e']
volume = [9,5,6,7,2]
V = 15

class Bin(object):
 def __init__(self):
    self.items = []
    self.sumVolume = 0
    self.auxvolumeSpace = 0

 def add(self, item, volume):
    self.items.append(item)
    self.sumVolume += volume
    self.auxvolumeSpace = self.sumVolume

 def __str__(self):
    # Printable representation
    return 'Bin(TotalVolume=%d, products=%s)' % (self.sumVolume, str(self.items))

if __name__ == '__main__':

def packAndShow(volume, maxVolume):

    bins = pack(volume, maxVolume)

    print('Solution using', len(bins), 'bins:')
    for i in bins:
        print(i)
    print('The total amount of bins needed, using the Best fit Algorithm is: ',len(bins))


def auxiliaryspace(volume, maxVolume):
 bins = []
 maxvolumespace = -1

 for bin in bins:
    if bin.sumVolume + volume <= maxVolume:
        bin.auxvolumeSpace += volume
        if bin.auxvolumeSpace >= maxvolumespace:
            maxvolumespace = bin.auxvolumeSpace
 return maxvolumespace


def pack(volume, maxVolume):
 bins = []
 for i in range(len(volume)):
    mv = auxiliaryspace(volume[i], maxVolume) 
    for bin in bins:
        if mv > 0 and bin.auxvolumeSpace == mv:
            bin.add(item[i], volume[i])
            break
    else:
        bin = Bin()
        bin.add(item[i], volume[i])
        bins.append(bin)

return bins


packAndShow(volume, V)

问题是所有物品都放在一个新的箱子里。结果如下：

Solution using 5 bins:
Bin(TotalVolume=9, products=['a'])
Bin(TotalVolume=5, products=['b'])
Bin(TotalVolume=6, products=['c'])
Bin(TotalVolume=7, products=['d'])
Bin(TotalVolume=2, products=['e'])
The total amount of bins needed, using the Best fit Algorithm is:  5

我认为问题出在“辅助空间”部分。我认为没有返回正确的值（我想要的）。有人可以帮忙吗？

4

0 回答 0