Find maximum size of rectangles to fill a container

Question

I have a container, of a certain width and height. I have a bunch of blocks that I need to fit in the container but I need to calculate the maximum size these blocks can be to fit.

For example:

to:

I guess its similar to this question but his code is jquery and applies to text. I would just like pseudocode or some form of algorithm of how to do this.

Answer 1

Assuming, as in the illustration, that all blocks have the same height and orientation, you can create an array A with the lengths of the blocks.

If the goal is to pack the blocks optimally in a given bounding rectangle, then solve the subset sum problem to find the set of blocks that is closest to the maximum length without being larger. Remove those blocks for the first row and repeat the process with the remaining blocks.

If the goal is to find the smallest (by area) bounding rectangle, then you should have a look at this paper: Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites. It also covers the case when the heights of the blocks may vary.

If the blocks can have different orientations, then the problem is a much harder packing problem.