3

我有一个矩形宽度 x 高度和 N 个相同未知大小的正方形。我必须确定这些正方形的最大尺寸以及行数和列数以完美地适合（UPD。我的意思是不要填充所有空间，而是尽可能多地填充空间）到矩形中。

我猜，在数学上它看起来像这样：

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= squares, 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++;
  }
}
4

2 回答 2

5

这个问题最近出现在我正在做的一个项目中。这是确定的解决方案：

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.
于 2016-07-25T12:32:09.050 回答
2

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

但是随后您给出了一个允许空白空间的示例最终结果。

那么它是哪一个？

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

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

于 2012-09-27T19:15:07.223 回答