algorithm - 瓦片(可扩展)堆叠算法

Question

问题来了。我有大小为 1 的矩形 Canvas 。因此它的坐标系为 (0.0 ... 1.0 - x 和 0.0 ... 1.0 - y)。

我也有一些瓷砖。瓷砖也是矩形的。它们有不同的大小，瓷砖的数量是一个变量。

我想在矩形 Canvas 中堆叠瓷砖，从 0.0 到 1.0(从左到右，从上到下):

1) 瓷砖必须适合 Canvas (但尽可能多地填充空间)

2) tiles 必须缩放(如果它们不合适)，每个 tile 应该缩放相同的量(它们必须保持相同的比例)。

3) 想象你手里拿着这个“瓷砖”，你把它们一个接一个地放在 Canvas 上

4) 它几乎像“TreeMap 算法” 但是 - 瓷砖的形状必须相同(矩形)并且我不需要填充 Canvas 的所有空间

有没有人可以用任何类似 C 的语言(C、C++、Java、C#)向我展示算法？

*我试过了。

1) 我计算了瓷砖的面积，然后我计算了瓷砖面积的总和(例如:我有两 block 瓷砖，一 block 面积为 2，另一 block 面积为 1，这意味着我的总和为 3)

2) 然后我计算每个瓷砖在“面积总和”中的“比例”(例如:2/3 和 1/3)

3) 然后通过Math.sqrt(x) 计算矩形 block 的大小(例如:Math.sqrt(2/3))

4) 然后一张一张地画瓷砖...

但这并不总是有效。有时我得到的瓷砖不在 Canvas 中..*

Answer 1

这可能看起来是一个打包问题，但是如果我们尝试完全按照它描述的那样解决这个问题，它就不是了。换句话说，没有解决方案，因为再一次，问题中所描述的没有问题。如果我们只有一个盒子和一组固定的图 block ，并且要求它们都必须适合盒子，那么就没有优化的余地。我可以看到几个相关的优化问题:

1.给定一组固定的瓷砖，这些瓷砖必须装入相同或不同尺寸的盒子中，找到最佳包装顺序，以便使用最少数量的盒子。

2.给定任意大小的单个盒子和一组图 block ，找到可以放入一个盒子的最佳(最大)图 block 集。

3.给定一个盒子和一组瓷砖 - 回答是否可以将它们放入盒子中的问题。

您要解决其中的哪一个问题？

现在设置问题的方式毫无意义，因为无论您将方 block 放入盒子中的顺序如何，无论它们如何排列，只要它们完全适合，它们将始终使用相同数量的空间。