I am aware that the general rectangle packing problem is NP-hard. I am trying to form an estimate for a version of the problem with constraints. Consider fitting rectangles of smaller size into a larger rectangle:
I am currently using the second method on the following webpage: https://cgi.csc.liv.ac.uk/~epa/surveyhtml.html : Next-Fit Decreasing Height (NFDH) algorithm and measuring the height of the smaller rectangles along the side and dividing it by the height of the overall rectangle. The measure that I am finding is not as accurate as I would like.
For my problem specifically, I have the following constraints that differ from the original:
- The size of all the boxes is known.
- The width will only ever be 2 rectangles wide (there will never be 3 in a row in the width direction).
- The rectangles placed together will ideally take up the greatest width possible.
- They are always packed such that a rectangle is placed as to take up the least length first. It will only be rotated to take up more space in the length direction if it is not possible to fit a smaller rectangle beside it.
- There will be no more than 30 rectangles added.
I am trying to optimize the following measure:
Estimate = (length of boxes on left side + length of boxes on right side) / (larger box length * 2)
(an average of the length of the boxes along either side)
Is anyone aware of an algorithm or can suggest an algorithmic approach to produce a more accurate estimate?