algorithm - 查找填充容器的最大矩形大小

Question

我有一个容器，有一定的宽度和高度。我有一堆块需要放入容器中，但我需要计算这些块可以容纳的最大尺寸。

例如：

到：

我猜它类似于这个问题，但他的代码是 jquery 并且适用于文本。我只想使用伪代码或某种形式的算法来说明如何做到这一点。

Answer 1

假设，如图所示，所有块具有相同的高度和方向，您可以创建一个包含A块长度的数组。

如果目标是将块最佳地打包在给定的边界矩形中，则解决子集和问题以找到最接近最大长度而不更大的块集。删除第一行的那些块，然后对剩余的块重复该过程。

如果目标是找到最小的（按区域）边界矩形，那么您应该看看这篇论文：Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites。它还涵盖了块的高度可能变化的情况。

如果块可以有不同的方向，那么问题是一个更难的包装问题。