13

Дана фигура (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);
}
13
  • Фигура А и фигура Б прямоугольники или произволные четырехугольники?
    – Kromster
    Commented 17 сент. 2015 в 14:41
  • Фигуры прямоульники, но могут быть и квадратами если размеры сторон одинаковы. Dmitriy Simushev - я обновил вопрос касательно вашего комментария.
    – walik
    Commented 17 сент. 2015 в 14:44
  • 4
    Тогда вам поможет habrahabr.ru/post/136225
    – Kromster
    Commented 17 сент. 2015 в 14:47
  • 3
    @VladD насколько я помню, данную задачу оптимально можно решить только полным перебором ..
    – Kromster
    Commented 18 сент. 2015 в 6:36
  • 1
    Вам нужно копать в сторону динамического программирования. Я не раз встречал такие задачи в теме динамического программирования. Commented 18 сент. 2015 в 11:07

5 ответов 5

2

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

  1. Если K=L, то F=(M mod K) * (N mod K).
  2. Если 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 способа в варианте со свободной центральной клеткой).

1

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

  • Считаем площадь основной фигуры (A) - S = M * N

  • Считаем площадь вкладываемой фигуры (B) - s = K * L

  • В итоге деления площадей фигуры (A) на (B) и отброса остатка, получаем количество вложенных прямоугольников

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

1
  • 2
    Если я не ошибаюсь, то это не верный алгоритм. Он не учитывает форму оставшегося пространства. Возьмем пример: Фигура А: M = 5 и N = 4; Фигура B: K = 2 и L = 2. При таком раскладе, поместятся максимум 4 фигуры. Но если просто делить площади как вы предложили, то получится 5 фигур (так как остается свободная полоса размером 1х4, то есть площадь 4, но форма не соответствует прямоугольнику, у которого форма 2х2, хотя площадь такая же).
    – walik
    Commented 8 окт. 2015 в 12:21
1

Нужно найти лучший вариант или идеальный? С идеальным - проблема. Например, берем квадрат 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. Наша функция должна вернуть количество прямоугольников в фигуре. В общем, типа перебираем несколько вариантов.

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

1

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

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

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

1
  • 3
    Неверно. Контрпример: большая фигура 3 × 3, маленькая 2 × 1. [a1/a2] * [b1/b2] = [3/2] * [3/1] = 1 * 3 = 3, [a1/b2] * [b1/a2] = [3/1] * [3/2] = 3, а правильный ответ — 4. Вы не учитываете повороты.
    – VladD
    Commented 28 окт. 2015 в 13:10
0

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

1
  • 4
    Неверно. Если основная фигура 1×1000, а вложенная фигура 2×2, вы не сможете поместить ни одной фигуры внутрь. Рассмотрение площадей недостаточно.
    – VladD
    Commented 17 окт. 2015 в 12:43

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.