algorithm - 将 1*2 和 1*3 的瓷砖尽可能多地放在 n*m 的地板上

Question

瓷砖可以旋转。

例子:

给定两 block 1*2 的瓷砖和一 block 1*3 的瓷砖，地板是 3*3，我们将所有瓷砖放入地板中，如下所示:

AAA
..B
CCB

现在，给定 n*m 层和 p 1*2 block 瓷砖和 q 1*3 block 瓷砖(瓷砖的数量是有限的)。返回可以放入地板的最大瓷砖数量。例如，答案是 3(你可以在地板上放 3 block 瓷砖)。

Answer 1

可能会有一些额外的复杂性，但这是我的想法:

• 用 1x2 的瓷砖填满整个地板。做起来应该很简单，只要确保它主要由平行的瓷砖组成，就像这样:(黑色和白色都是瓷砖)

  

  请注意，我只是用水平瓷砖而不是垂直瓷砖填充底行，这只是为了填充网格。左下方的图 block 是空的(您可能希望将其右侧的图 block 替换为 1x3 的图 block )。

• 如果您没有那么多 1x2 的图 block ，仍然完全填满网格，它们将在下一步中被移除。

• 虽然您没有足够的 1x2 拼贴来放置，但系统地用 2 个 1x3 拼贴替换 3 个平行的 1x2 拼贴。所以:

  变成