Hints with same-rectangles-in-rectangle packing al

问题:

I've been tasked with building a program for an acquaintance, that calculates the best way to fit book pages on a large paper to be printed and cut.

In practice, that means I need to find the best way to arrange rectangles with identical dimensions (the pages) inside a given rectangle (the printing paper) in such a way that guillotine cuts can be used to separate all pages without ruining any.

If any of you can point my searches to a better direction, either by giving me links or a more accurate wording of the problem's name (terminology-wise), that would be great. I've narrowed the terminology down to '2D packing problem with identical rectangles in a rectangle and guillotine limitations.'

回答1:

I was facing a similar issue and finally got the answer to my problem on my own. Assuming length is greater than the breadth for both the rectangles (smaller and larger ones), following are the possibilities while you try to pack smaller rectangles on the larger one. Let the length of larger rectangle be L, its breadth be B and length and breadth of smaller rectangles be l and b respectively.

Case 1: Pack the smaller rectangles such that their lengths are parallel to the breadth of the larger rectangle until you fall short of space. Then try the other way round (Length of larger rectangle parallel to Lengths of smaller one) on the available space.

Case 2: Pack the smaller rectangles such that their lengths are parallel to the length of the larger rectangle until you fall short of space. Then try the other way round (Length of larger rectangle parallel to breadths of smaller one) on the available space.

Take the maximum of case 1 and case 2 to get the maximum no of smaller rectangles that can be packed on a larger one. Find the python 3 code of the implementation here: http://geekzonelive.blogspot.in/2016/06/packing-similar-small-rectangles-into.html

回答2:

This is a classical packing problem reducible to knapsack problem. The popular version is called Cutting stock problem since it involves industrial processes of cutting papers (like your problem). The problem is NP hard, and one uses integer programming (combinatorial optimization) methods to solve them. There are more general packing problems on the packing article. I think you will find more rectangles here.