矩形のサイズを計算するためのアルゴリズムが必要

Question

私は論理的な謎を解き、それを解決するには効率的なアルゴリズムが必要です。

サイズがw * h（幅*高さ）の大きな長方形（ボックス）があります。

私はまた、大きさではなく固定比率の他の長方形をx個持っています。

Xを取得する最速の方法は、Xの各矩形の最大サイズをボックス内に入れる（大きな矩形）ことができますか？

例：

ボックス矩形サイズは150×50（幅*高さ）及びiは25の小さな長方形を有しています。

小さい矩形の固定割合は3です（高さ= 5の場合は幅= 5 * 3 = 15）。 長方形xの高さを呼び出します。

すべての矩形を大きな矩形に（ボックス内に）挿入することができる最大のXを探したいと思います。

（小さな矩形は、行と列に配置され、例えば5列および5行比率と最大高さによって）

誰もがこの問題を解決するための効率的なアルゴリズムを知っていますか？

Answer 1

ええと何ですか？

ちょうど（w * h）/ 75ではないですか？

ええ、かっこは必要ありませんが、それはあなたが望むものではありませんか？あるいは、私はここに何かを逃していますか？

ここで、wとhは、大きな矩形または親矩形の寸法です。 75は3 * 25です。

Answer 2

私は、解析的にではなく経験的にこの問題を解決しようとしています（つまり、*を説明します）。本質的には、その矩形がその最大サイズになるように小さな矩形を配置したいと考えています（最大サイズは矩形の最大値で定義できます。つまり、すべての矩形を可能な限りの大きさに配置しようとすると、その解決策の1つが最適な解決策になります。また、これは実際には、矩形の高さと幅が比率によって決まるため、1つの次元的な問題です。暗黙的に他方を設定します。

* - すべての可能性を言ったとき、私は本当に最も合理的な可能性を意味しました。私たちは浮動小数点空間にあるので、すべての可能性をテストすることはできません。より細かく細かい精度をテストすることはできますが、すべてのサイズをテストすることはできません。これにより、私たちが試みるrectのサイズを反復するステップサイズを定義します。ステップサイズと、これは非常に長い時間のために実行することができる矩形の数に基づいて

const float STEP_SIZE = 0.0001; 
float fLastTotalSize = 0; 

int main() 
{ 
    PlaceRect(myRects.begin(), myRects.end()); 
} 

void PlaceRect(Iterator currentRect, Iterator end) 
{ 
    if (currentRect == end) 
    { 
    return; 
    } 

    float fRectMaxSize = CalculateMaxPossibleRectSize(*currentRect); 

    // find the number of steps it will take to iterate from the smallest 
    // rect size to the largest 
    int nSteps = fRectMaxSize/STEP_SIZE; 

    for(int i = 0; i < nSteps; ++i) 
    { 
    // based on the step index scale the rect size 
    float fCurrentRectTestSize = i*STEP_SIZE; 

    currentRect->SetSize(fCurrentRectTestSize); 

    float fTotalSize = CalculateTotalSizesOfAllRects(); 
    if (fTotalSize > fLastTotalSize) 
    { 
     fLastTotalSize = fTotalSize; 
     SaveRectConfiguration(); 
    } 

    // Continue placing the rest of the rects assuming the size 
    // we just set for the current rect 
    PlaceRect(currentRect + 1, end); 

    // Once we return we can now reset the current rect size to 
    // something else and continue testing possibilities 
    } 
} 

が、あなたの経験的な解決策を見つけるでしょう。