需要一个算法来计算矩形的大小

Question

我遇到了一个逻辑谜题，我需要一个有效的算法来解决它。

我有一个大矩形（盒子），尺寸为宽*高（宽*高）。

我还有其他一些没有大小但比例固定的矩形。

获得使每个 X 矩形在框（大矩形）内具有最大尺寸的 x 的最快方法是什么？

示例：

盒子矩形大小为 150* 50（宽 * 高），我有 25 个小矩形。

小矩形的固定比例为3（如果高度=5则宽度=5*3=15）。 我们将矩形的高度称为 x。

我想找到最大的 X，它可以让我将所有矩形插入到大矩形（框内）中。

（小矩形将按行和列放置，例如按比例和最大高度放置 5 列和 5 行）

有谁知道解决此问题的有效算法吗？

Answer 1

嗯什么？

不就是(w*h)/75吗？

是的，不需要括号......但这不是你想要的吗？还是我在这里遗漏了一些东西？

其中 w 和 h 是大矩形或父矩形的尺寸。
75 就是 3*25。

Answer 2

我会尝试凭经验解决这个问题（使用 回溯 解决）而不是分析性地解决，即找到所有可能性*（我将解释*）。本质上，我们希望将每个矩形从该矩形可以达到的最大尺寸开始放置（最大尺寸可以由矩形在碰到其邻居的起点或增长到容器主矩形之前可以达到的最大尺寸来定义）。这意味着，如果我们尝试将每个矩形放置在其所有可能的大小中，那么这些解决方案之一将是最佳解决方案。另请注意，这实际上是一个一维问题，因为矩形的高度和宽度受比率限制；设置其中一个就隐式设置另一个。

* - 当我说所有可能性时，我真正的意思是最合理的可能性。由于我们处于浮点空间中，我们无法测试所有可能性。我们可以测试越来越精细的精度，但无法测试所有尺寸。因此，我们定义了一个步长来迭代我们将尝试的矩形的大小。

const float STEP_SIZE = 0.0001;
float fLastTotalSize = 0;

int main()
{
  PlaceRect(myRects.begin(), myRects.end());
}

void PlaceRect(Iterator currentRect, Iterator end)
{
  if (currentRect == end)
  {
    return;
  }

  float fRectMaxSize = CalculateMaxPossibleRectSize(*currentRect);

  // find the number of steps it will take to iterate from the smallest 
  // rect size to the largest
  int nSteps = fRectMaxSize / STEP_SIZE;

  for(int i = 0; i < nSteps; ++i)
  {
    // based on the step index scale the rect size
    float fCurrentRectTestSize = i*STEP_SIZE;

    currentRect->SetSize(fCurrentRectTestSize);

    float fTotalSize = CalculateTotalSizesOfAllRects();
    if (fTotalSize > fLastTotalSize)
    {
      fLastTotalSize = fTotalSize;
      SaveRectConfiguration();
    }

    // Continue placing the rest of the rects assuming the size 
    // we just set for the current rect 
    PlaceRect(currentRect + 1, end);

    // Once we return we can now reset the current rect size to 
    // something else and continue testing possibilities 
  }
}

根据步长和矩形数量，这可能会运行很长时间，但会为您找到经验解决方案。