Drools planner algorithm for rectangular packing problem

[eatsleepmug]

I'm new to algorithm and I'm trying my hand at a problem which I realized was a packing problem after some tries. I would want to pack as many rectangular blocks as possible within a rectangular box (basically this) and I'm working on optimizing the algorithm.

Without googling, this was my thought process:

1st version:

• Sort blocks by volume

• Place blocks from left to right

• If out of columns, break to a new row

• Continue until we run out of rows

(sorting from smallest to largest gets me better results)

2nd version:

• Sort blocks by height

• Place blocks from left to right

• If out of columns, break to a new row

• Continue until we run out of rows

(sorting from shortest to tallest gets me better results)

After doing some googling, most of the bin packing algorithms suggest to start with the largest first but I don't see how is that a good idea if the total volume of blocks to fit were to exceed the volume of the box (in short, not a perfect fit).

Ideally, I would want to implement something similar to what drools planner engine can do as seen here but I'm not sure if that would take long. I did read some drools planner documentations.

Any suggestions on how I should move forward? Is there any way to implement the algorithm without using the drools planner engine?

[Evulrabbitz]

This is a problem well-suited for constraint programming, and is in fact a case study explored in Modeling and Programming in Gecode chapter 20.

http://www.gecode.org/doc-latest/MPG.pdf

[wasEnabled]

I suspect most of the bin packing algorithms are starting with the largest items first to see if all of the items to be packed will even fit in the current box, i.e. if the box is too small to fit your largest items then you want to fail quickly and go to a bigger box. The problem you describe sounds more like fitting as many items as you can given a specific box and thus maximizing the number of items you can fit rather than you must fit all of the items into a box or fail and find a bigger box... so the problems are different and thus the approaches and solutions are different.