0

我有 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

有没有办法让我得到所有可能的包装？

这感觉像是一个装箱挑战，但我并不是试图找到一个“最佳”解决方案，而是所有（或至少多个）可能的解决方案。

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

有任何想法吗？

4

1 回答 1

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

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

于 2013-09-11T03:12:46.860 回答