Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 :)

share|improve this question

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.

share|improve this answer
When looking at fixed widths of {25%, 33%, 50%, 66%, 75%}, the problem is not NP complete. – ccoakley Mar 26 '12 at 2:07
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. – ccoakley Mar 26 '12 at 2:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.