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

瓷砖可以旋转。

例子:

给定两个1 * 2瓷砖和一个1 * 3瓷砖，并且地板为3 * 3，我们将所有瓷砖放入地板中，如下所示:

AAA
..B
CCB

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

最佳答案

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

AAACD
BBBCD
EF.CD
EFGGG
EFHHH

而这是无法通过替换来实现的。

那该怎么办呢？我已经做了大量的数学工作，并且非常了解它。我会给你一些提示:

首先放置1 * 3瓦片，然后放置1 * 3，以便我们可以放置尽可能多的1 * 2(实际上，假设地板上有n个未覆盖的瓦片，这样我们就可以放置地板( n/2)1 * 2个图块)。

注意一些极端情况。例如，所有图块均为1 * 3，地板为1 * 10，地板为2 * 10，依此类推。

如果您有任何问题，请给我评论。

关于algorithm - 尽可能将1 * 2和1 * 3瓷砖放在n * m地板上，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16697874/