我如何收拾在2D盒子俄罗斯方块式的多个矩形 [英] How do i pack multiple rectangles in a 2d box tetris style

问题描述

我有一些不同的宽度和高度的矩形。我有一个较大的矩形平台，把他们的。我想这样他们š$ P $垫在纵向（X）的尺寸将其打包在平台的一侧，但保留宽度（Y）的尺寸到最小。这是把他们像一个俄罗斯方块游戏。不能有任何重叠，但可以存在差距。是否有一个算法，在那里做呢？

I have a number of rectangles of various widths and heights. I have a larger rectangular platform to put them on. I want to pack them on one side of the platform so they spread in the lengthwise (X) dimension but keep the widthwise (Y) dimension to a minimal. That is to place them like a tetris game. There can be no overlaps but there can be gaps. Is there an algorithm out there to do this?

推荐答案

听起来像斌的变化包装< /一>：

Sounds like a variation of Bin Packing:

在计算复杂性理论，   在装箱问题是一个   组合NP问题。在里面，   不同体积的对象必须是   打成仓有限数量   容量V在最小化的一种方式   用箱的数量。

In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used.

有许多这样的变化   问题，诸如2D填料，线性   包装重量包装，由包装   成本，等等。他们有许多   应用，如填充   集装箱，装载卡车的重量   能力，创建文件备份   可移动媒体和技术制图   在FPGA实现定制   硬件。

There are many variations of this problem, such as 2D packing, linear packing, packing by weight, packing by cost, and so on. They have many applications, such as filling up containers, loading trucks with weight capacity, creating file backup in removable media and technology mapping in FPGA implementation of custom hardware.

这是对可能的解决方案，在同一页引述：

A quote from the same page about possible solutions:

既然是NP难的，最有效的已知算法使用   启发式完成结果   这虽然在大多数情况下非常好，   可能不是最佳的解决方案。对于   例如，第一拟合算法   提供了一个快速，但往往非最佳   解决方案，包括将每个项目   到第一区，用来将它   适合。它需要Θ（N log n）的时间，   其中n是元件与数   包装。该算法可以由   由第一分选有效得多   元素列表成减小   顺序（有时被称为   首次适应递减算法），   虽然这并不能保证一个   最优解，并且对于较长的列表   可能增加的运行时间   算法。

Since it is NP-hard, the most efficient known algorithms use heuristics to accomplish results which, though very good in most cases, may not be the optimal solution. For example, the first fit algorithm provides a fast but often nonoptimal solution, involving placing each item into the first bin in which it will fit. It requires Θ(n log n) time, where n is the number of elements to be packed. The algorithm can be made much more effective by first sorting the list of elements into decreasing order (sometimes known as the first-fit decreasing algorithm), although this does not guarantee an optimal solution, and for longer lists may increase the running time of the algorithm.

我建议你遵循从维基百科页面的一些链接。此外，通过谷歌搜索装箱算法，你可能会发现很多相关的信息。

I suggest you follow some links from that Wikipedia page. Also, by Googling "bin packing algorithm" you'll probably find a lot of relevant information.

这篇关于我如何收拾在2D盒子俄罗斯方块式的多个矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！