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

いくつかの解が繰り返されていることがわかります。これは、入力に同じ数値が 2 つあるためです。

于 2013-09-11T03:12:46.860 に答える