8

这是问题所在。我有大小为 1 的矩形画布。所以它的坐标系为（0.0 ... 1.0 - x 和 0.0 ... 1.0 - y）。

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

我想在矩形画布中堆叠瓷砖，从 0.0 到 1.0（从左到右，从上到下）：

1）瓷砖必须适合画布（但要尽可能多地填充空间）

2) 必须缩放图块（如果它们不适合），每个图块应按相同的量缩放（它们必须保持相同的比例）。

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

4）它几乎像“TreeMap算法”但是 - 瓷砖的形状必须相同（矩形），我不需要填充画布的所有空间

这是我想要得到的

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

*我试过这个。

1）我计算了瓷砖的面积，然后我计算了瓷砖面积的总和（例如：我有两个瓷砖，一个面积为 2，另一个面积为 1，这意味着我的总和为 3）

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

3) 然后通过 Math.sqrt(x) 计算矩形块的大小（例如：Math.sqrt(2/3)）

4）然后一张一张地画瓷砖……

但这并不总是有效。有时我会让瓷砖脱离画布..*

4

5 回答 5

4

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

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

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

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

您要解决其中的哪一个？

现在设置问题的方式是没有意义的，因为无论您将瓷砖放在盒子中的哪种顺序，它们将始终使用相同数量的空间，无论它们如何排列，当然只要它们都适合。

于 2011-03-12T19:02:54.457 回答
2

尝试蒙特卡罗算法：

Repeat until result is good enough or until you aren't seeing any improvement
  Select (with removal) a random first tile
  Place the first tile at a random position
  Repeat until no remaining tiles
    Select (with removal) a random tile
    Place it adjoining to the existing "tile blob" 
      (you might have to do a search here to find the best place to plug it in)
  Check to see if you have a new best filled-area percentage

所有随机瓷砖选择都应按瓷砖面积加权，以便您倾向于首先放置较大的瓷砖。

于 2011-03-10T14:32:10.957 回答
2

我不认为这是一个 (bin)-packing 问题，因为我为 1D bin-packing 问题写了一个。我认为这里的问题是通过 2D-cutting-stock 问题解决的，也许还有 2D-bin-packing。你想要的也是尝试背包问题。这个问题很难解决（NP）并且没有解决方案。这有点像 Travelsalesman 问题，其中解决方案的数量与城市数量成指数关系。如果您可以将复杂性降低为一维问题，您可以在 phpclasses.org 上尝试我的装箱算法。

于 2011-03-12T20:06:59.607 回答
1

正如其他人指出的那样 - 问题描述不是很清楚。但是我假设您可以根据需要缩放每个图块（至少您的示例表明可以进行图块缩放）。所以我的解决方案很简单（但可能不是你想要的也不是最优的）：

  • 按因子缩放每个图块：
    EDGE空间/ (EDGE tile * N ½ )
  • 将每个图块放在当前行中，如果图块超出空间限制 - 前进到下一行。

这是大于或等于瓷砖总数的N最接近的完美正方形。

ps 如果您需要在瓷砖之间留出一些间距 - 只需将上述比例因子缩小一点即可。

希望有帮助。

于 2011-03-15T12:43:03.947 回答
0

我不确定这是否是您想要的，但您可以查看 TreeMap 算法。

树状图

维基百科定义

C++ 实现

于 2011-03-07T16:28:26.143 回答