如何用正方形块完全填充一个固定的矩形？

Question

这是背包算法还是装箱算法？我找不到确切的解决方案，但基本上我有一个固定的矩形区域，我想用完美的正方形填充它，这些正方形代表我的物品，其中每个物品都有不同的重量，这会影响它们相对于其他物品的大小。

它们将从左上到右下从大到小排序。

另外，即使我需要完美的正方形，最终也允许一些非均匀缩放填充整个空间，只要它们仍然保留其相对面积，并且非均匀缩放是用尽可能少的量完成的。

我可以使用什么算法来实现这一目标？

Answer 1

Hiroshi Nagamochi 和 Yuusuke Abe提出了一种快速近似算法。我用 C++ 实现了它，注意获得最坏情况的 O(n log n) 时间实现，最坏情况的递归深度为 O(log n)。如果 n \xe2\x89\xa4 100，这些预防措施可能是不必要的。

\n

#include <algorithm>\n#include <iostream>\n#include <random>\n#include <vector>\n\nnamespace {\n\nstruct Rectangle {\n  double x;\n  double y;\n  double width;\n  double height;\n};\n\nRectangle Slice(Rectangle &r, const double beta) {\n  const double alpha = 1 - beta;\n  if (r.width > r.height) {\n    const double alpha_width = alpha * r.width;\n    const double beta_width = beta * r.width;\n    r.width = alpha_width;\n    return {r.x + alpha_width, r.y, beta_width, r.height};\n  }\n  const double alpha_height = alpha * r.height;\n  const double beta_height = beta * r.height;\n  r.height = alpha_height;\n  return {r.x, r.y + alpha_height, r.width, beta_height};\n}\n\nvoid LayoutRecursive(const std::vector<double> &reals, const std::size_t begin,\n                     std::size_t end, double sum, Rectangle rectangle,\n                     std::vector<Rectangle> &dissection) {\n  while (end - begin > 1) {\n    double suffix_sum = reals[end - 1];\n    std::size_t mid = end - 1;\n    while (mid > begin + 1 && suffix_sum + reals[mid - 1] <= 2 * sum / 3) {\n      suffix_sum += reals[mid - 1];\n      mid -= 1;\n    }\n    LayoutRecursive(reals, mid, end, suffix_sum,\n                    Slice(rectangle, suffix_sum / sum), dissection);\n    end = mid;\n    sum -= suffix_sum;\n  }\n  dissection.push_back(rectangle);\n}\n\nstd::vector<Rectangle> Layout(std::vector<double> reals,\n                              const Rectangle rectangle) {\n  std::sort(reals.begin(), reals.end());\n  std::vector<Rectangle> dissection;\n  dissection.reserve(reals.size());\n  LayoutRecursive(reals, 0, reals.size(),\n                  std::accumulate(reals.begin(), reals.end(), double{0}),\n                  rectangle, dissection);\n  return dissection;\n}\n\nstd::vector<double> RandomReals(const std::size_t n) {\n  std::vector<double> reals(n);\n  std::exponential_distribution<> dist;\n  std::default_random_engine gen;\n  for (double &real : reals) {\n    real = dist(gen);\n  }\n  return reals;\n}\n\n} // namespace\n\nint main() {\n  const std::vector<Rectangle> dissection =\n      Layout(RandomReals(100), {72, 72, 6.5 * 72, 9 * 72});\n  std::cout << "%!PS\\n";\n  for (const Rectangle &r : dissection) {\n    std::cout << r.x << " " << r.y << " " << r.width << " " << r.height\n              << " rectstroke\\n";\n  }\n  std::cout << "showpage\\n";\n}\n

\n

\n