Maximum number of $m\times n$ rectangles that fit in a $k \times k$ square

Question

I'm sure this has been asked before but I have searched for ages and can't quite find what I'm looking for. Here's the problem:

Essentially what is the maximum possible number of rectangles of a given size $(m \times n)$ that will fit without overlapping in a given sized square ($k \times k$).

How can you tackle it?

Answer 1

In general, this kind of packing problem is very difficult. Of course there is an obvious upper bound of $\lfloor k^2/(mn) \rfloor$ from consideration of areas, and a lower bound of $\lfloor k/m \rfloor \lfloor k/n \rfloor$. There can be a lot of room between these.

See e.g. Recursive partitioning approach for the Manufacturer's Pallet Loading Problem.