Variation des Rucksacks ... in Python

Question

Ich habe ein konzeptionelles Problem, wo ich mehrere Pakete habe, jedes Paket enthält eine Reihe von Elementen im Inneren. Elemente sind vom Typ A oder Typ B. Ich möchte die Pakete in einer endlichen Anzahl von Bins so verteilen, dass sich die Verteilung zwischen A und B nicht stark unter den Bins unterscheidet.

Das Problem ist ziemlich komplex, daher werde ich versuchen, es mit harten Einschränkungen und einem konzeptuellen Beispiel zu erklären.

Constraints

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 

Beispiel (Conceptual)

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` 

Gesamtverteilung als solches 302 * A und 191 * B 493 Proben insgesamt ergibt und dann die sich ergebenden Verhältnisse sind 61,25% von A und 38,75% von B

Gewünschtes Ergebnis:

A minimierte Satz von Chargen, wobei jede Charge höchstens 3 bins (Länge < = 92) enthält, die mit sagen sie zwischen 52 und 60 vom Typ A und zwischen 32 und 40 vom Typ B (die kombinierte Summe nicht über 92) pro Fach.

Frage

Was Algorithmus oder Verfahren würde man dieses Problem angehen vorschlägt, ist ein einfaches vorgeschlagene Schema tun wird (wenn man bedenkt, dass, was ich bisher versucht (siehe unten) erhält nicht sehr weit)

Die Idee hinter meinen versuchen bisher

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 

Das ist auch, wo ich stecken bin, das momentan nicht minim nicht versuchen, Stellen Sie die Anzahl der Fächer ein und überprüfen Sie nicht die Verhältnisse. Außerdem habe ich die quälende Idee, dass die Art und Weise, wie ich das versuche, nicht annähernd der kluge Weg ist, ein solches Problem zu lösen.

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)