將方塊包裝成長方形

我有一個長方形寬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 =空space`。

事實上，我看到了類似的問題，但具有預定義的正方形大小。另外，我寫了一些笨拙的算法，但它的結果非常不滿意..

編輯：我現在的算法：

我嘗試了很多的變化，但我不能讓所有的情況下工作得很好。其實，我可以通過所有可能的尺寸，但我不喜歡這種方法。

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

來源

2012-09-27 DizzyBlack

請發表您寫的算法，並描述結果如何不令人滿意。它太慢了嗎？結果不是你所期望的嗎？如果是這樣，你會得到什麼結果，你期望得到什麼結果？ – Kevin

完成。感謝您的回覆 – DizzyBlack

我*認爲*我明白你的意思，但可以肯定的是，你可以包括一些例子嗎？（只需要數字就可以）假設你有一個24x60的矩形和N = 10，這個方塊的大小可以是12，對吧？如果N = 2，大小24？ – harold

你的問題是不一致的。首先，您將問題描述爲「確定這些方塊的最大尺寸以及行數和列數，以便完美地將裝入矩形中。」（強調增加）。

但是，然後你給了一個樣本最終結果，允許空的空間。

那它是哪一個呢？

如果您需要將矩形完全適合矩形，且沒有空白區域，並且沒有方形超出矩形的邊界，那麼最大方形的大小將等於矩形的長度和寬度的最大公約數長方形。

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

來源

2012-09-27 19:15:07 mbeckish

對不起。我的意思是不要填滿所有的空間，但儘可能多地填充空間。感謝您的回覆。我無法理解它的一件事 - 這種方法只能給我最大的尺寸，但我也有預定義的數量的方塊，我需要放置。 – DizzyBlack

@DizzyBlack - 嗯，你知道你不想要任何一個小於最大公約數的正方形。所以，如果所有的矩形和正方形長度都是整數，那麼你可以嘗試gcd和min（長度，寬度）之間的所有正方形長度。 – mbeckish

好吧，我不確定這是我搜索的完美解決方案，但無論如何，謝謝，我會考慮一下。 – DizzyBlack

這個問題在一個項目我工作最近出現了。這裏是確定的解決方案：

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-25 12:32:09

將方塊包裝成長方形

回答

相關問題