Packing known number of uniform-sized squares into a known rect

[pitonyak]

If you state that s must be an integer, then I guess that I missed it, so i will assume that it is not an integer.

You know that the total area is given by wh and that there are n squares. Divide wh by n and you have the maximum size for each square. So, you can set an upper bound on s as (s^2 <= w * h / n).

We are not using an integer for s, so we know that there will be an exact fit on either the width or the height. So, take the square root of (w * h / n) and set this to s.

Let a = w / s - floor(w/s)
Let b = h / s - floor(h/s)

No time to finish my thoughts, and I have not worked this out, but, I am thinking about reducing s such that either w / s or h / s is an integer (which should be a simple calculation). Uggg!

[pitonyak]

The entire floor thing is not correct I think. I believe the following to be true (assuming s is known):

w/s * floor(h/s) <= n <= w / s * ceiling(h/s) <= w / s * h / s = w*h / s^2

I think that I would explore an initial guess of s as D = sqrt(w * h / n), then do something silly like

We know that s <= D.

E = min(h / ceiling(h/D), w / ceiling(w/D))

E is designed such that either h/E or W/E is an integer. The point to note is that this provides a value for s such that it completely fills one of the dimensions. My guess is that (if there is no rounding) that this will provide you with the optimal solution.