提示具有断头台限制的相同矩形包装中的矩形？ [英] Hints with same-rectangles-in-rectangle packing algorithm with guillotine limitation?

问题描述

我的任务是为一个熟人构建一个程序，该程序可以计算出将书页适合在要打印和裁切的大纸上的最佳方式。

在实践中，这意味着我需要找到一种最佳方法，以便在给定的矩形（打印纸）内排列具有相同尺寸（页面）的矩形，以便可以使用断头台切割来分隔所有页面而不会破坏任何页面。 / p>

如果任何人都可以通过给我链接或对问题名称的准确措辞（用术语表示）将我的搜索指向更好的方向，那将是大。我已经将术语的范围缩小为在矩形中具有相同矩形并且具有断头台限制的2D包装问题。

解决方案

面对类似的问题，最后我自己解决了问题。
假设长度都大于两个矩形（较小和较大的矩形）的宽度，则在尝试将较小的矩形打包在较大的矩形上时，可以使用以下方法。
假设较大矩形的长度为L，宽度为B，较小矩形的长度和宽度分别为l和b。

案例1：打包较小的矩形，使其长度与较大的矩形的宽度平行，直到空间不足为止。然后在可用空间上尝试另一种方法（较大的矩形的长度与较小的矩形的长度平行）。

情况2：打包较小的矩形，使其长度为平行于较大矩形的长度，直到空间不足为止。然后在可用空间上尝试另一种方法（大矩形的长度与小矩形的宽度平行）。

以案例1和案例2中的最大值为准。最多可以装在较大矩形上的较小矩形的最大数量。
在此处找到实现的python 3代码： http://geekzonelive.blogspot.in/2016/06/packing-like-small-rectangles-into.html

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.'

解决方案

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

这篇关于提示具有断头台限制的相同矩形包装中的矩形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！