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

Question

瓷砖可以旋转。

例子：

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

AAA
..B
CCB

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

Answer 1

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

• 用 1x2 的瓷砖填充整个地板。它应该很简单，只要确保它主要由平行的瓷砖组成，像这样：（黑色和白色都是瓷砖）

  

  请注意，我只是用水平瓷砖而不是垂直填充底行，这只是为了填充网格。左下角的瓷砖是空的（你可能想用一个 1x3 的瓷砖替换它右边的瓷砖）。

• 如果您没有那么多 1x2 瓷砖，仍然完全填充网格，它们将在下一步中被删除。

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

  变成

Answer 2

杜克林的答案是错误的。考虑一个 5*5 的地板和 8 个 1*3 的瓷砖。将所有瓷砖放入地板的唯一方法是：

AAACD
BBBCD
EF.CD
EFGGG
EFHHH

而这不能通过更换来实现。

那么该怎么做呢？我做了很多数学工作并且很清楚。我会给你一些提示：

1. 先放 1*3 块，再放 1*3，这样我们就可以放 1*2 尽可能多的（其实假设地板有 n 块裸露的瓷砖，这样我们可以放/2) 1*2 格子)。
2. 小心一些极端情况。例如，所有的瓷砖都是 1*3，地板是 1*10，地板是 2*10 等等。

如果您有任何问题，请给我留言。

Answer 3

目前尚不清楚要返回什么。您需要解决方案集还是只需要最大数量？一种简单的解决方案可能只使用 1*2 块。显然，1*2 的瓷砖可能比 1*3 的瓷砖更多。

假设b=0

a = n * m div (1*2)

假设a=0, m>=3,n>=3

b = n * m div (1*3)