将正方形装进矩形

Question

我有一个矩形，宽度为x，高度为height，并且有N个相同大小的正方形。我必须确定这些正方形的最大尺寸以及行数和列数，使其完美地适合矩形（更新：我指的不是填满所有空间，而是尽可能填满空间）。

我猜数学上看起来是这样的：

x * size <= width                  //x - number of columns
y * size <= height                 //y - number of rows
x * y <= N                         //N - number of squares
size -> max                        //size - size of squares

最终结果可能如下所示：

1 1 1 1
1 1 1 1
1 1 0 0

其中1代表方块，0代表空格。

实际上我看到过类似的问题，但是这些问题都有预定义的方块大小。我写了一些笨拙的算法，但是它的结果非常不令人满意。

编辑：我的当前算法：

我尝试了很多变化，但是我无法让它在所有情况下都完美地工作。实际上，我可以遍历所有可能的大小，但我不喜欢这种方法。

// to make things more simple I put width as bigger size 
int biggerSize = this.ClientSize.Width;
int lowerSize = this.ClientSize.Height;  
int maxSize = int.MinValue;
int index = 0;
int index2 = 0;

// find max suitable size
for (int i = _rects.Count; i > 0; i--) {
  int size = biggerSize / i;
  int j = (int)Math.Floor((double)lowerSize / size);

  if (i * j >= _boards.Count && size > maxSize) {
    maxSize = size;
    index = (int)i;
    index2 = (int)j;
  }
}

int counter = 0;

// place all rectangles
for (int i = 0; i < index; i++) {
  for (int j = 0; j < index2; j++) {
    if (counter < _rects.Count) {                                
      _rects[counter].Size = new Size(maxSize, maxSize);
      _rects[counter].Location = new Point(i * maxSize, j * maxSize);
    }

    counter++;
  }
}

- DizzyBlack

---

请发布您编写的算法，并描述结果为何不令人满意。速度太慢吗？结果与您预期的不同吗？如果是这样，那么您得到了什么结果，您期望得到什么结果？ - Kevin

我认为我理解你的意思，但为了确保，你能否包含一些例子？（只需要数字即可）比如说你有一个24x60的矩形，N=10，那么正方形的大小可以是12，对吗？如果N=2，大小为24？ - harold

是的，没错。如果N=9且24x60，则会有一个空方块。我表述目标有点不正确——不是完美填充，而是最佳可能的填充。 - DizzyBlack

Answer 1

最近我在一个项目中遇到了这个问题。以下是解决方案：

int numItems; // the number of squares we need to pack in.
double rectWidth; // the width of the space into which we want to pack our squares.
double rectHeight; // the height of the space into which we want to pack our squares.

double tableRatio = rectWidth / rectHeight;
double columns = sqrt(numItems * tableRatio);
double rows = columns / tableRatio;

columns = ceil(columns); // the number of columns of squares we will have
rows = ceil(rows); // the number of rows of squares we will have

double squareSize = rectWidth / columns; // the size of each square.

- Ryan W

Answer 2

您的问题不一致。首先，您将问题陈述为“确定这些正方形的最大尺寸以及行数和列数，使其完全适合矩形。”（强调添加）。

但是，您给出了一个允许留有空白空间的样本最终结果。

那么到底是哪一个呢？

如果您需要正方形完全适合矩形而没有空白空间，并且没有正方形超出矩形的边界，则最大正方形的尺寸将等于矩形的长度和宽度的最大公约数。

请参见http://en.wikipedia.org/wiki/Greatest_common_divisor#A_geometric_view。

- mbeckish

---

抱歉，我的意思不是填满所有空间，而是尽可能填满空间。 谢谢您的回复。我只有一个疑问 - 这种方法只会给我最大的尺寸，但我还有预定义的需要放置的正方形数量。 - DizzyBlack

@DizzyBlack - 嗯，你知道你不想要任何小于最大公约数的正方形。因此，如果所有矩形和正方形的长度都是整数，那么你可以尝试所有在最大公约数和最小长度（length、width中的较小值）之间的正方形长度。 - mbeckish

好的，我不确定这是我寻找的完美解决方案，但无论如何，谢谢，我会考虑一下。 - DizzyBlack