0

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:

enter image description here

to:

enter image description here

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.

Community
  • 1
  • 1
Shawn Mclean
  • 56,733
  • 95
  • 279
  • 406

1 Answers1

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.

PengOne
  • 48,188
  • 17
  • 130
  • 149
  • Re: Subset sum problem, so use the first block and keep resizing it until it is has the maximum width that can fit in the container, then check that size against the others and if they don't fit, just decrease and repeat? – Shawn Mclean Jan 22 '12 at 07:13