algorithm - 寻找多种装箱解决方案

Question

我有 3 个大小可变的盒子:

A: 5, B: 3, C: 6

我有尺寸为 a: 1, b: 2, c: 2, d: 3, e: 5

我显然可以将它们放入以下模式:

A: a, b, c
B: d
C: e

但你也可以这样做:

A: e
B: a, b
C: c, d

有没有一种方法可以获得所有可能的包装？

这感觉像是装箱挑战，但我并不是要寻找“最佳”解决方案，而是要寻找所有(或至少多个)可能的解决方案。

我想我可能会以随机顺序对项目运行简单的装箱算法，直到找到解决方案，但这似乎效率很低......

有什么想法吗？

Answer 1

我刚刚实现了你的要求

boxSizes, itemSizes = [5, 3, 6], [1, 2, 2, 3, 5]

def recurse(boxes, itemIndex, solution, itemsUsed):
    global itemSizes
    if itemsUsed == len(itemSizes):
        print solution
        return
    for i in range(len(boxes)):
        for j in range(itemIndex, len(itemSizes)):
            if boxes[i] - itemSizes[j] >= 0:
                boxes[i] -= itemSizes[j]
                solution[i].append(itemSizes[j])
                recurse(boxes, j + 1, solution, itemsUsed + 1)
                solution[i].pop()
                boxes[i] += itemSizes[j]

recurse(boxSizes, 0, [[] for i in range(len(boxSizes))], 0)

输出

[[1, 2, 2], [3], [5]]
[[2, 3], [1, 2], [5]]
[[2, 3], [1, 2], [5]]
[[5], [1, 2], [2, 3]]
[[5], [1, 2], [2, 3]]
[[2, 2], [3], [1, 5]]
[[2, 3], [2], [1, 5]]
[[2, 3], [2], [1, 5]]
[[5], [2], [1, 2, 3]]
[[5], [2], [1, 2, 3]]
[[5], [3], [1, 2, 2]]

我们看到一些解决方案重复，这是因为输入中有两个相同的数字。