时间戳

首页 > 解决方案 > 将少量包裹装入固定数量的箱中

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

问题描述

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

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

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

number_of_bins = 3

箱的大小（包装的包裹大小的总和）可以在 0 到 2 之间变化（也就是说，箱中的包裹大小之和的差必须相等或几乎相等）。[1,2]因此，使用(=3) 和[2](=2) （差异为 1）的垃圾箱很好，而使用[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]

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

模拟：

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

导致

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

标签： pythonalgorithm

解决方案

这是使用纸浆的解决方案：

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 ]))

推荐阅读