Dgdrxrt

I have a variable number of small rectangles which are natively 39 x 83 (width by length).

I will also have an arbitrary sized, container rectangle that I need to fit all of the smaller rectangles into. I can resize the small rectangles but I must preserve their aspect ratio and they must all be the same size as each other.

The goal is to resize them such that I cover the maximum possible area of the container rectangle. The small rectangles can not overlap each other or extend outside of the container rectangle.

I feel like this should be a straightforward problem well within my capability of solving - but after struggling with it for 2 days, consulting with my grade 9 son and performing a couple of dozen Google searches, I’m ready to ask for help.

What is the correct way to approach this problem?

I will assume all the small rectangles have to have the same orientation. It is already hard and I give a thought if this is not true at the end. Let the bounding rectangle be $W times H$. We are trying to choose a scale factor $s$ for the $39 times 83$ rectangles that is as large as possible so that we can fit $N$ scaled rectangles in the bounding one.

Assuming the small rectangles have to have the same orientation means the optimum tiling is rectangular. We just have to choose the orientation of the small rectangles and the number that fit across the width.

As a first cut, assume the small rectangles are oriented with the long axis horizontal. They are then $83s$ wide and $39s$ tall, so we get $lfloor frac W83s rfloor$ rectangles horizontally and $lfloor frac H39srfloor$ vertically. We need $lfloor frac W83s rfloorlfloor frac H39srfloorge N$ for the proper number to fit. We start by ignoring the floor signs, so we can find $s=sqrtfrac WH83cdot 39 N$. This just expresses the fact that the small rectangles have to have less area than the large one, ignoring any problems about whether they fit.

At this point you will only succeed if $frac W83s$ and $frac H39s$ are integers, so the outer rectangle is completely filled. You are lucky-declare victory! If not, you have an approximation $n=frac W83s$ to the number of small rectangles you want horizontally. If you place $m$ rectangles horizontally, you need $k=lceil frac Nm rceil$ rows. You can compute the scale factors in each direction as $frac W83m$ and $frac H39k$. Take the lower of these. Now search for the best $m$, which will be near the $n$ we computed above, based on finding the largest scale factor.

Repeat the process for the other orientation of the small rectangles, exchanging $39$ and $83$ and you have the answer under these restrictions.

If you don't insist that the small rectangles have the same orientation, you have one more degree of freedom. You can split $N$ into $N=K+M$ and have $K$ small rectangles in vertical orientation and $M$ in horizontal orientation. You want either the heights or the widths of the two rectangles to be close, but there is more searching to do.