Максимальное количество прямоугольников, помещающихся в другом прямоугольнике

#алгоритм #геометрия

Дана фигура (A) размером M на N.
Дана вторая фигура (B), поменьше, размером K на L.

Нужно определить, сколько максимально фигур B поместятся в фигуре A. Они должны располагаться
одна рядом с другой, часть фигур может располагаться вертикально, другая часть горизонтально,
что бы занять максимальное возможное пространство в основной фигуре.

Кто то может подсказать что то по этому вопросу?



На данный момент у меня мысли только если: 

считать количество прямоугольников, расположенных горизонтально, которые поместятся
горизонтально в фигуре, то есть ставим прямоугольник, рядом второй, заполняем линию,
дальше снизу ставим еще одну линию, и так до самого низа. 

Далее справа, возможно, останется пространство. Проверяем, помещается ли туда прямоугольник
вертикально, если да, то заполняем стобец вертикальными прямоугольниками. 

В итоге получаем число -- сколько поместилось прямоугольников. 

Далее повторяем тоже самое, только располагаем изначально прямоугольники вертикально,
и если снизу остается пространство, проверяем, помещаются ли туда прямоугольники горизонтально,
если да, то заполняем линию. И опять считаем сколько поместилось. 

Из двух подсчетом выбираем тот, который дал наибольшый результат.

Вот пример подсчета, который я описал, реализованный на на JavaScript:

function calcFigures(FigureA, FigureB) {
    var total1 = 0,
        total2 = 0;

    (function() {
        var figures_per_row = Math.floor(FigureA.width / FigureB.width),
            figures_per_col = Math.floor(FigureA.height / FigureB.height),
            invers_figures_per_row = 0,
            invers_figures_per_col = 0;

        if (FigureA.width - (figures_per_row * FigureB.width) >= FigureB.height) {
            invers_figures_per_row = Math.floor((FigureA.width - (figures_per_row
* FigureB.width)) / FigureB.height);
            invers_figures_per_col = Math.floor(FigureA.height / FigureB.width);
        }

        total1 = (figures_per_row * figures_per_col) + (invers_figures_per_row *
invers_figures_per_col);
    }());

    (function() {
        var figures_per_row = Math.floor(FigureA.width / FigureB.height),
            figures_per_col = Math.floor(FigureA.height / FigureB.width),
            invers_figures_per_row = 0,
            invers_figures_per_col = 0;

        if (FigureA.width - (figures_per_row * FigureB.height) >= FigureB.width) {
            invers_figures_per_row = Math.floor((FigureA.width - (figures_per_row
* FigureB.height)) / FigureB.width);
            invers_figures_per_col = Math.floor(FigureA.height / FigureB.height);
        }

        total2 = (figures_per_row * figures_per_col) + (invers_figures_per_row *
invers_figures_per_col);
    }());

    return Math.max(total1, total2);
}

    

Ответы

Ответ 1

Существуют очевидные оценки для количества R прямоугольников KxL (K>=L), которое
можно разместить внутри прямоугольника MxN (сторона M - снизу).


Если K=L, то F=(M mod K) * (N mod K).    
Если K>L, то F >= max(F1,F2), где
F1 = (M mod K) * (N mod L) + ((M%K) mod L) * (N mod K),
F2 = (N mod K) * (M mod L) + ((N%K) mod L) * (M mod K).    


Оценка F1 соответствует варианту, при котором левая часть большого прямоугольника
по максимуму закладывается длинной стороной K вдоль стороны M, а оставшаяся правая
часть - с разворотом.
Оценка F2 получается, если стороны M и N поменять ролями.   

При этом максимальная оценка F определяется площадями прямоугольников, т.е.
F <= MN mod KL.

P.S. В рамках указанных оценок можно применить комбинаторный перебор.
Например, в случае (5x5,3x2) 3 <= F <= 4, и можно поискать наилучшую укладку по следующему
алгоритму:
1) вычислить количество свободных клеток при F=4 (одна клетка);
2) задать цикл по всем вариантам размещения свободных клеток (без учёта симметрии
- 25 вариантов);
3) перебрать все способы размещения фигур (сверху вниз, слева направо, без разворота
и с разворотом), не оставляющие дополнительных свободных клеток (2 способа в варианте
со свободной центральной клеткой).


Ответ 2

Если актуально то в данном случае подойдет алгоритм:


Считаем площадь основной фигуры (A) - S =  M * N
Считаем площадь вкладываемой фигуры (B) - s = K * L 
В итоге деления площадей фигуры (A) на (B) и отброса остатка, получаем количество
вложенных прямоугольников 


если нужно могу реализовать на python'e функцию


Ответ 3

Считаешь площадь основной фигуры,считаешь площадь вложенной фигуры и берешь модуль
вложенной фигуры из основной(операция %).


Ответ 4

Нужно найти лучший вариант или идеальный?
С идеальным - проблема.
Например, берем квадрат 5*5 и фигуры 2*3. Мы можем разместить 4 фигуры на 24 клетки.
Это идеальное решение. А можно ли его получить автоматическим методом - я не знаю.
Теперь про определение лучшего результата. 
Я предлагаю такой алгоритм:

Берем большую фигуру. Делим вертикальной линией так, чтобы в левую часть укладывались
маленькие фигуры горизонтально, а в правую часть - вертикально. 
Вариантов проведения таких линий будет несколько, так что надо будет просчитать каждый
вариант. 

То есть для фигуры 23*17 и мелкой 4*3 получаем получаем варианты
4+19
8+15
12+11
16+7
20+3

Берем вариант (8 + 15) клеток у нас получается 2 фигуры 8*17 и 15*17
Далее разворачиваем каждый из прямоугольников и вызываем саму функцию рекурсивно
для каждого из прямоугольников, то есть 8*17 и 15*17. Наша функция должна вернуть количество
прямоугольников в фигуре. 
В общем, типа перебираем несколько вариантов.

Для оптимизации можно для прямоугольника, описываемой парой чисел, запоминать максимальное
количество, которое у нас получилось, чтобы по несколько раз не вычислять сколько фигур
влезает в такой прямоугольник.


Ответ 5

пусть:
большая фигура BIG = a1 * b1
малая фигура SMALL = a2 * b2

кол-во фигур SMALL которые поместятся в BIG: это будет максимальное значение из вот
таких двух

целое(a1/a2) * целое(b1/b2)
и
целое(a1/b2) * целое(b1/a2)