Минимальные прямоугольники, необходимые для покрытия данной прямоугольной области

Я имею прямоугольную область измерения: n*m. У меня также есть меньший прямоугольник размера: x*y. Какое будет минимальное количество меньших прямоугольников, необходимых для покрытия всей площади большего прямоугольника?

Не нужно упаковывать меньшие прямоугольники. Они могут перекрываться друг с другом, если необходимо, пересекают границы большего прямоугольника. Единственное требование состоит в том, что мы должны использовать наименьшее количество прямоугольников x*y.

Другое дело, что мы можем поворачивать меньшие прямоугольники, если требуется (под углом 90 градусов), чтобы минимизировать число.

n, m, x и y: все являются натуральными числами. x, y не обязательно должны быть факторами n, m.

Я не мог решить это в указанное время, и не мог найти подход. Я начал с рассмотрения различных случаев, когда n, m делится на x, y или нет.

Обновление

Примеры тестовых случаев:

  • n * m = 3 * 3, x * y = 2 * 2. Результат должен быть 4
  • n * m = 5 * 6, x * y = 3 * 2. Результат должен быть 5
  • n * m = 68 * 68, x * y = 9 * 8. Результат должен быть 65

Ответы

Ответ 1

(ОБНОВЛЕНИЕ: см. Более новую версию ниже.)

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

Вы начинаете с базовой сетки, как это:

tiling - basic grid

и оптимальное решение примет одну из этих двух форм:

solution type 1 solution type 2

Таким образом, для каждой из этих точек вы рассчитываете количество требуемых плиток для обоих вариантов:

all grid points

Это очень простая реализация. Значения "по горизонтали" и "по вертикали" в результатах - это количество плиток в не повернутой зоне (обозначено на изображениях розовым цветом).

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

(Тестирование показало, что вам нужно запустить алгоритм во второй раз с переключенными параметрами x и y, и что проверка обоих типов решений действительно необходима.)

function rectangleCover(n, m, x, y, rotated) {
    var width = Math.ceil(n / x), height = Math.ceil(m / y);
    var cover = {num: width * height, rot: !!rotated, h: width, v: height, type: 1};
    for (var i = 0; i <= width; i++) {
        for (var j = 0; j <= height; j++) {
            var rect = i * j;

            var top = simpleCover(n, m - y * j, y, x);
            var side = simpleCover(n - x * i, y * j, y, x);
            var total = rect + side + top;
            if (total < cover.num) {
                cover = {num: total, rot: !!rotated, h: i, v: j, type: 1};
            }
            var top = simpleCover(x * i, m - y * j, y, x);
            var side = simpleCover(n - x * i, m, y, x);
            var total = rect + side + top;
            if (total < cover.num) {
                cover = {num: total, rot: !!rotated, h: i, v: j, type: 2};
            }
        }
    }
    if (!rotated && n != m &&  x != y) {
        var c = rectangleCover(n, m, y, x, true);
        if (c.num < cover.num) cover = c;
    }
    return cover;

    function simpleCover(n, m, x, y) {
        return (n > 0 && m > 0) ? Math.ceil(n / x) * Math.ceil(m / y) : 0;
    }
}
document.write(JSON.stringify(rectangleCover(3, 3, 2, 2)) + "<br>");
document.write(JSON.stringify(rectangleCover(5, 6, 3, 2)) + "<br>");
document.write(JSON.stringify(rectangleCover(22, 18, 5, 3)) + "<br>");
document.write(JSON.stringify(rectangleCover(1000, 1000, 11, 17)));