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 に答える