想象一下，你有一个画布，在这个画布中已经有一些对象。您如何找到用正方形覆盖“未覆盖”区域的最小方法，而不是相互重叠，完全填满画布。
在我的例子中，“画布”是一个 html-div 容器，对象是嵌套的 div 容器。可能看起来像这样：http ://www.encodechain.com/demo/200908_optimize.png 左边是“开始”，右边是可能的第一个“步骤”......
我知道有一个算法可以解决这个问题，但目前我不记得名字了。
问问题
142 次
2 回答
2
我能找到的最好的是这篇论文：Tiling a rectangle with the minimum squares。这篇论文读起来很有趣，尽管有时它会通过谈论“通用常数”来深入研究理论领域。我不确定“大小为 m x n 的矩形是否可以用 k 个正方形平铺”的问题是否是 NP 完全的。正如在另一个回复中指出的那样，您的问题类似于 NP 完全的包装问题。而且，当然，您的问题是本文中解决的问题的概括，因为您正在处理非矩形区域。您可以首先将您的区域分成最少数量的矩形，这本身就是另一个有趣的问题。最后，即使你能有效地做到这一点，我
正如作者所说，贪心算法是一个很好的起点：只要放下最大的正方形，直到该区域被填满。
于 2009-08-13T06:31:35.997 回答