Изменение рюкзака... в python - программирование

У меня есть концептуальная проблема, когда у меня есть несколько пакетов, каждый пакет содержит несколько элементов внутри. Элементы имеют тип A или тип B. Я хочу распространять пакеты в конечном количестве бункеров таким образом, чтобы распределение между A и B не сильно отличалось от ящиков.

Проблема довольно сложная, поэтому я попытаюсь объяснить ее жесткими ограничениями и концептуальным примером.

Ограничения

A package can only be used once
A package must be used entirely
The bins should have relatively equal distributions between `A` and `B` (max 5% deviation from the original ratio)
A package can be spread across all the bins in the given batch
I want to end up with as little as batches (size <= 3 bins) as possible

Пример (концептуальный)

Plate 1: 92 * `A`
Plate 2: 92 * `A`
Plate 3: 64 * `A`
Plate 4: 42 * `A`, 50 * `B`
Plate 5: 12 * `A`, 49 * `B`
Plate 6: 92 * `B`

Общее распределение как таковое составляет 302 * A и 191 * B, что дает 493 выборки, тогда полученные отношения составляют 61,25% от A и 38,75% от B

Желаемый результат:

Минимизированный набор партий, где каждая партия содержит не более 3 бункеров (длина <= 92), скажем между 52 и 60 типа A и между 32 и 40 типа B (общая сумма не выше 92).

Вопрос

Какой алгоритм или метод предложит решить эту проблему, простую предложенную схему (учитывая, что то, что я пытался до сих пор (см. ниже), не очень далеко)

Идея моих попыток пока

data = ... # This is a list containg all values in a tuple format of `(unit, [(type, location)])` format
while len(data) > 0:
   batch = []
   counter1 = 0
   counter2 = 0
   for i in data:
      for j in i[1]:
         if j[0] == 'A':
            counter1 += 1
         else:
            counter2 += 1
   ratio1 = counter1/(counter1+counter2)
   ratio2 = counter2/(counter1+counter2)
   # Now we know the maximum number of A and B per batch
   counter3 = 0 # This keeps track of howmany type `A` we have in current batch
   counter4 = 0 # This keeps track of howmany type `B` we have in current batch
   while counter3 < ratio1:
      for i in data:
         for j in i[1]:
            if Counter(elem[0] for elem in j)['A'] < (ratio1 - counter3) and Counter(elem[0] for elem in j)['B'] < (ratio2 - counter4):
               # Add this unit (from data) to the batch
               batch.append(i)
               counter3 += Counter(elem[0] for elem in j)['A']
               counter4 += Counter(elem[0] for elem in j)['B']
               # Remove the used unit from data

Это также место, где я застрял, в настоящее время он не пытается свести к минимуму количество ящиков и не проверяет коэффициенты. Кроме того, у меня есть ворчащая идея, что способ, которым я пытаюсь это сделать, - это не то, что рядом с умным способом решения такой проблемы.

Ответ 1