Finding multiple solutions to bin packing

Question

I have 3 boxes of variable size:

A: 5, B: 3, C: 6

I have items of size a: 1, b: 2, c: 2, d: 3, e: 5

I could obviously fit them in the following pattern:

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

but you could also do it like this:

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

Is there a way I can get all possible packings like this?

This feels like a bin packing challenge but I'm not trying to find an "optimal" solution, just all (or at least multiple) possible solutions.

I imagine I could maybe run a naive bin packing algorithm over the items in a random order until a solution is hit but that seems really inefficient...

Any ideas?

Answer 1

I just implemented what you asked for

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)

Output

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

We see some solutions repeating, that is because there are two numbers in the inputs which are same.