Algorithm for determining grid based on variably sized "blocks"?

Question

I'm trying to convert a set of "blocks" in to a grid-like layout. The blocks have a width of either 25%, 33%, 50%, 66%, or 75% of their container and each row of the grid should try to fit as many blocks as possible, up to a total width of 100%.

I've discovered that trying to do this while leaving no remaining blocks in the original set is very hard. Eventually, I think my solution will be to upgrade/downgrade various block sizes (based on their priority or something) so they all fit in to a row.

Either case, before I do that, I thought I'd check if someone has some code (or a paper) demonstrating a solution to this problem already? And bonus points if the solution incorporates varying block heights in to its calculations :)

Answer 1

This is an NP-complete problem- there are no known polynomial time algorithms in the general case. It is known as Bin Packing or Subset Sum.

• ccoakley: When looking at fixed widths of {25%, 33%, 50%, 66%, 75%}, the problem is not NP complete.
• ccoakley: It's also worth pointing out that subset sum is not strongly NP-complete, so if the input domain is small, dynamic programming will solve instances of Subset Sum quickly.