algorithm - 简化的矩形包装算法。能够从更大的形状池中进行选择。

Question

我有一个 200 宽和 100 高的矩形。我有一个由 50 个矩形和盒子组成的混合池。矩形有 20x40 和 40x20 等形状。这些盒子的形状为 20x20 和 40x40。因此，假设我想在这个更大的矩形中放置最多数量的框和矩形，以便不留空间。除了 bin 打包算法或矩形打包算法之外，我如何实现它。如果我应该选择其中一种算法，是否有适合这种情况的良好实现？

Answer 1

首先，我们可以稍微抽象一下这个问题：

具有 10*5 网格的表格。我们用 1*1,1*2,2*1 填充表格（1*2 和 2*1 被认为是相同的？），2*2 瓷砖。

我们可以忽略 1*1，因为它适用于任何情况。

如果我们认为 1*2 和 2*1 是相同的：

这种情况有点简单。只需将 2*2 放在一起。然后我们会得到：

xxxxxxxxxx
xxxxxxxxxx
xxxxxx....
xxxxxx....
..........

我们只是把 1*2 放在这样的地方：

xxxxxxxxxx
xxxxxxxxxx
xxxxxxAABB
xxxxxxCCDD
EEFFGGHHII

您可以检查该策略是否适用于任何情况。

如果 1*2 或 2*1 不考虑相同？

然后它会有点复杂。也许存在像上面这样的优雅解决方案，但很难找到和证明。考虑到这张桌子有多小，我们可以通过一些修剪来进行完整的搜索，我认为它会起作用。