将正方形打包成矩形

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

我想,从数学上看,它看起来像这样:

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

最终结果可能如下所示:

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

其中1 = squares0 =空的空间`。

实际上我看到了类似的问题,但预定义的正方形大小。 另外,我写了一些笨拙的算法,但结果却非常不理想。

编辑:我当前的算法:

我尝试了很多变化,但我不能让它完美地适用于所有情况。 实际上,我可以通过所有可能的尺寸,但我不喜欢这种方法。

 // 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++; } } 

你的问题不一致。 首先,您将问题说明为“确定这些方块的最大大小以及完全适合矩形的行和列数”。 (重点补充)。

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

那是哪个呢?

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

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

最近在我正在开展的一个项目中出现了这个问题。 以下是确定的解决方案:

 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.