Simplified rectangle packing algorithm. Being able to pick from bigger pool of shapes.

Question

I have a rectangle with 200 width and 100 height. I have a mix pool of 50 rectangles and boxes. The rectangles comes in shapes like 20x40, and 40x20. The boxes will come in shapes of 20x20 and 40x40. So lets say If I want to fit the highest number of boxes and rectangles in this bigger rectangle in order to leave no space. How I can achieve it other that bin packing algorithm or rectangle packing algorithm. And if I should pick one of those algorithms, is there a good implementation out there for this scenario ?

Answer 1

First of all, we can abstract the problem a little bit:

A table with 10*5 grids. And we fill the table with 1*1,1*2,2*1(1*2 and 2*1 is considered the same?),2*2 tiles.

We can ignore the 1*1 because it's can fit into any cases.

If the we consider 1*2 and 2*1 is the same:

This case is somehow simple.Just put 2*2 together. Then we wiil get:

xxxxxxxxxx
xxxxxxxxxx
xxxxxx....
xxxxxx....
..........

we just put 1*2 in such a way:

xxxxxxxxxx
xxxxxxxxxx
xxxxxxAABB
xxxxxxCCDD
EEFFGGHHII

You can check that strategy works for any cases.

If 1*2 or 2*1 is not consider the same?

Then it will be a little bit complex. Maybe there exists a elegant solution like above, but it's hard to find and prove. Considering the table is some how small we can just do a complete search with some pruning and I think it will be works.