Algorithm to get maximum number of n rectangles with given same width and height that fit into a rectangle with a given width and height

Question

I am looking for an algorithm that can return the maximum number of rectangles in the same size with given width and height that fit in to a rectangle with given height and width.

For an example let's say I have a small rectangle with height of 50mm and width of 70mm and a bigger rectangle with height of 1200mm and width of 1000mm. I want to arrange the small rectangles inside the bigger rectangle in a fully utilize way. The small rectangles can be arrange in anyway (Small rectangle can rotated as well), I just want the number of small rectangles that I can put in the bigger rectangle in a maximum utilize way.

Thank you for your help!

Answer 1

In your example, you can form a rectangle of 1,000 x 1,050 leaving 1,000 x 150, then a rectangle of size 150 x 980, leaving 150 x 20, which is less than a small rectangle, and therefore cannot be improved.

In general, this will be hard and involve systematically trying out various combinations.

Answer 2

If you want to take only positive integer sides into consideration, you can take a value that yields the highest possible quotient with a non-zero remainder. The best thing to do here (I am not that sure, but let it be so :D)is to take the remainder as $1$ , subtract it from the longer side of the larger rectangle and find the remaining number's smallest proper divisor. If the side minus one yields a length that has a prime number as its magnitude, subtract another $1$ from the value you have at hand and do the above steps. But please take care not to end up in a place where the next dividend you take can be divided by the remainder at hand - that's where you can put a decision point whether to abort that iteration or not.

Another thing is that the smaller side must either be divisible or leave a small remainder when divided by the remainder.

I am not sure if this helps, but I felt this would work. Please do notify me if I did the wrong thing.