python - 将少量包裹装入固定数量的箱子

Question

我有一个包装尺寸列表。最多会有大约 5 种不同的尺寸，它们可能会出现几次 (<50)。

packages = [5,5,5,5,5,5,10,11]

我需要将它们打包到固定数量的箱子中，例如 3 个。

number_of_bins = 3

垃圾箱的大小(打包包裹的大小总和)可能在 0 和 2 之间变化(也就是说，垃圾箱中包裹的大小总和之差必须相等或几乎相等).因此，使用 [1,2] (=3) 和 [2] (=2)(差异为 1)的 bin 很好，使用 [ 10] (=10) 和 [5] (=5) (区别是 5)不是。

可以不将所有包裹分类到垃圾箱中，但我想要的解决方案是保留最少数量的包裹未打包。

所以在这种情况下(我认为)最好的解决方案是

bins = [11,5],[10,5],[5,5,5]
remaining = [5]

可能有一种背包或装箱算法可以做到这一点，但我还没有找到。我可以强行使用它，但我不确定这样做的有效方法是什么。

有什么有效的方法可以轻松做到这一点吗？我只是错过了相关的搜索词来找到它吗？

---

另一个例子:

packages = [5,10,12]
number_of_bins = 2

导致

bins = [12],[10]
remaining = [5]

因为

bins = [12],[10,5]

bin 大小为 12 和 15，相差超过 2。

模拟:

packages = [2,10,12]
number_of_bins = 3

导致

bins = [2],[],[]
remaining = [12,10]

Answer 1

这是一个使用 pulp 的解决方案:

from pulp import *

packages = [18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 65, 65, 65]
number_of_bins = 3
bins = range(1, number_of_bins + 1)
items = range(0, len(packages))

x = LpVariable.dicts('x',[(i,b) for i in items for b in bins],0,1,LpBinary)
y = LpVariable('y', 0, 2, LpInteger)
prob=LpProblem("bin_packing",LpMinimize)

#maximize items placed in bins
prob.setObjective(LpAffineExpression([(x[i,b], -3) for i in items for b in bins] + [(y, 1)]))

#every item is placed in at most 1 bin
for i in items:
    prob+= lpSum([x[i,b] for b in bins]) <= 1

for b in bins:
    if b != 1: # bin 1 is the one with lowest sum
        prob+= LpAffineExpression([(x[i,b], packages[i]) for i in items]  + [(x[i,1], -packages[i]) for i in items])  >= 0
    if b != number_of_bins: # last bin is the one with highest
        prob+= LpAffineExpression([(x[i,number_of_bins], packages[i]) for i in items]  + [(x[i,b], -packages[i]) for i in items])  >= 0

#highest sum - lowest sum <= 2 so every difference of bin sums must be under 2
prob += LpAffineExpression([(x[i,number_of_bins], packages[i]) for i in items]  + [(x[i,1], -packages[i]) for i in items]) <= 2  
prob += LpAffineExpression([(x[i,number_of_bins], packages[i]) for i in items]  + [(x[i,1], -packages[i]) for i in items]) == y

prob.solve()
print(LpStatus[prob.status])

for b in bins:
    print(b,':',', '.join([str(packages[i]) for i in items if value(x[i,b]) !=0 ]))
print('left out: ', ', '.join([str(packages[i]) for i in items if sum(value(x[i,b]) for b in bins) ==0 ]))