Дана фигура (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);
}