Изменение рюкзака ... в python

Question

У меня есть концептуальная проблема, когда у меня есть несколько пакетов, каждый пакет содержит несколько элементов внутри. Элементы имеют тип 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 

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

Answer 1

#quick generator to rotate bin numbers 
def getBin(maxBin): 
    number = -1 
    while True: 
     number +=1 
     if number >= maxBin: 
      number = 0 
     yield number 

batches = [] 
data = .... 

#calculate the minimum number of bins we need 
numberOfBins = (len(data))/ 92 + 1 

aBinPlacement = getBin(numberOfBins) 
bBinPlacement = getBin(numberOfBins) 

bins = numberOfBins * [[]] 

#the ratio will be maintained because we rotate bins by type 
for datum in data: 
    if datum[0] == 'A': 
     bins[aBinPlacement.next()].append(datum) 
    else: 
     bins[bBinPlacement.next()].append(datum) 

batches.extend(bins)