Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

1 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.

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

 
discard

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.