Алгоритм наилучшего соответствия Python - - PullRequest
Новая
       34

Алгоритм наилучшего соответствия Python -

0 голосов
/ 25 сентября 2018

Я пытаюсь создать наилучший алгоритм для упаковки в мусорное ведро.Проблема с упаковкой бункеров: минимизируйте количество бункеров, используемых для упаковки предметов, учитывая объемную емкость.

То, что должна делать эта эвристика, это

  1. Попробуйте поместить элемент всамая полная корзина, в которой она будет размещена, т. е. корзина, в которой будет оставлено наименьшее пространство, оставшееся

  2. Если корзина не найдена, начните новую корзину.

Чтобы написать это, я сделал вспомогательный том.Для элемента, который вы хотите разместить, добавьте громкость в каждую корзину.Бункер с наибольшим объемом (который все еще выполним) получит предмет.Я попробовал следующее в 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

Я думаю, что проблема где-то в части «вспомогательного пространства».Я не думаю, что верное значение (которое я хочу) возвращается .. Может кто-нибудь помочь, пожалуйста?

...