1

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

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.

  • 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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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