1

I'm looking to solve a problem regarding the optimal sorting of variable sized boxes into the confined space of a 4x4 sized rack. The algorithm should sort those boxes so that there is as little wasted rackspace as possible.

The rack I'm talking about looks like the typical IKEA rack "Expedit".

Perhaps somebody can point me to documentation on algorithms that could solve such a problem or to some implementation. Every programming language is welcome.

Thanks for your time, Frank

thenoseman
  • 1,180
  • 1
  • 11
  • 12
  • Thanks @Eric and @epitaph for your pointers. I've been expecting a hard to solve problem. But that's the fun of it, right? And it ain't homework. It's me trying to optimize my rack full of boardgames :) – thenoseman Apr 11 '11 at 18:32

2 Answers2

1

What you are looking to do is solve the 2d bin-packing problem.

Here's a question with some pointers.

Community
  • 1
  • 1
Eric Conner
  • 10,422
  • 6
  • 51
  • 67
  • I don't think this is a 2d problem because each cell is the same width? – Micromega Apr 10 '11 at 19:18
  • hmm.. i didn't look carefully enough at the question the first time through, but he may actually want the 3D bin packing problem (that is if he wants to put multiple boxes of different dimensions in each cell) – Eric Conner Apr 10 '11 at 22:45
  • Maybe - the question isn't clear enough. It could be even homework. – Micromega Apr 10 '11 at 22:56
1

You want to look for the 1d bin-packing problem (and NOT the 2d bin-packing). This problem is very hard to solve. You want to read this: http://www.developerfusion.com/article/5540/bin-packing/. Here is a 2d version: Packing problem revisited

Community
  • 1
  • 1
Micromega
  • 12,486
  • 7
  • 35
  • 72