背包的变化......在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

这也是我被卡住的地方,目前这并不是要尽量减少垃圾箱的数量,也不会检查比率.另外,我有一个唠叨的想法,即我试图做到这一点的方式并不是解决这个问题的聪明方法.

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)