覆盖给定矩形区域所需的最小矩形

Question

我有一个矩形的维度区域: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

Answer 1

（更新：请参阅下面的新版本。）

我认为（但目前我没有证据）不规则的平铺可以被丢弃，找到最佳解决方案意味着找到切换平铺方向的点。

您从这样的基本网格开始：

最佳解决方案将采用以下两种形式之一：

因此，对于每个点，您可以计算两个选项所需的图块数量：

这是一个非常基本的实现。结果中的“水平”和“垂直”值是非旋转区域中的图块数量（图像中以粉红色表示）。

该算法可能会检查某些事情两次，并且可以使用一些记忆来加快速度。

（测试表明，您需要在交换 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)));

这是 Evgeny Kluev 提供的反例：(68, 68, 9, 8) 返回 68，而有一个仅使用 65 个矩形的解决方案，如下图所示：

更新：改进算法

反例展示了算法的推广方式：从 4 个角开始工作，尝试所有独特的方向组合以及区域之间边界 a、b、c 和 d 的每个位置；如果中间有一个矩形未被覆盖，请尝试两个方向来覆盖它：

下面是这个想法的一个简单的、未经优化的实现；它可能多次检查某些配置，11×17/1000×1000 测试需要 6.5 秒，但它为反例和上一个版本的其他测试找到了正确的解决方案，因此逻辑似乎是合理的。

这些是代码中使用的五次旋转和区域编号。如果大矩形是正方形，则只检查前3次旋转；如果小矩形是正方形，则仅检查第一次旋转。X[i]和Y[i]是区域i中矩形的大小，w[i]和h[i]是区域i的宽度和高度，以矩形的数量表示。

function rectangleCover(n, m, x, y) {
    var X = [[x,x,x,y],[x,x,y,y],[x,y,x,y],[x,y,y,x],[x,y,y,y]];
    var Y = [[y,y,y,x],[y,y,x,x],[y,x,y,x],[y,x,x,y],[y,x,x,x]];
    var rotations = x == y ? 1 : n == m ? 3 : 5;
    var minimum = Math.ceil((n * m) / (x * y));
    var cover = simpleCover(n, m, x, y);

    for (var r = 0; r < rotations; r++) {
        for (var w0 = 0; w0 <= Math.ceil(n / X[r][0]); w0++) {
            var w1 = Math.ceil((n - w0 * X[r][0]) / X[r][1]);
            if (w1 < 0) w1 = 0;
            for (var h0 = 0; h0 <= Math.ceil(m / Y[r][0]); h0++) {
                var h3 = Math.ceil((m - h0 * Y[r][0]) / Y[r][3]);
                if (h3 < 0) h3 = 0;
                for (var w2 = 0; w2 <= Math.ceil(n / X[r][2]); w2++) {
                    var w3 = Math.ceil((n - w2 * X[r][2]) / X[r][3]);
                    if (w3 < 0) w3 = 0;
                    for (var h2 = 0; h2 <= Math.ceil(m / Y[r][2]); h2++) {
                        var h1 = Math.ceil((m - h2 * Y[r][2]) / Y[r][1]);
                        if (h1 < 0) h1 = 0;
                        var total = w0 * h0 + w1 * h1 + w2 * h2 + w3 * h3;
                        var X4 = w3 * X[r][3] - w0 * X[r][0];
                        var Y4 = h0 * Y[r][0] - h1 * Y[r][1];
                        if (X4 * Y4 > 0) {
                            total += simpleCover(Math.abs(X4), Math.abs(Y4), x, y);
                        }
                        if (total == minimum) return minimum;
                        if (total < cover) cover = total;
                    }
                }
            }
        }
    }
    return cover;

    function simpleCover(n, m, x, y) {
        return Math.min(Math.ceil(n / x) * Math.ceil(m / y),
                        Math.ceil(n / y) * Math.ceil(m / x));
    }
}

document.write("(3, 3, 2, 2) &rarr; " + rectangleCover(3, 3, 2, 2) + "<br>");
document.write("(5, 6, 3, 2) &rarr; " + rectangleCover(5, 6, 3, 2) + "<br>");
document.write("(22, 18, 5, 3) &rarr; " + rectangleCover(22, 18, 5, 3) + "<br>");
document.write("(68, 68, 8, 9) &rarr; " + rectangleCover(68, 68, 8, 9) + "<br>");

更新：修复了中心区域的计算

正如@josch在评论中指出的，上面的代码中中心区域4的宽度和高度的计算没有正确完成；有时它的大小被高估，从而导致矩形的总数被高估。发生这种情况的一个示例是 (1109, 783, 170, 257)，它返回 23，而存在 22 的解。下面是一个新的代码版本，其中正确计算了区域 4 的大小。

function rectangleCover(n, m, x, y) {
    var X = [[x,x,x,y],[x,x,y,y],[x,y,x,y],[x,y,y,x],[x,y,y,y]];
    var Y = [[y,y,y,x],[y,y,x,x],[y,x,y,x],[y,x,x,y],[y,x,x,x]];
    var rotations = x == y ? 1 : n == m ? 3 : 5;
    var minimum = Math.ceil((n * m) / (x * y));
    var cover = simpleCover(n, m, x, y);

    for (var r = 0; r < rotations; r++) {
        for (var w0 = 0; w0 <= Math.ceil(n / X[r][0]); w0++) {
            var w1 = Math.ceil((n - w0 * X[r][0]) / X[r][1]);
            if (w1 < 0) w1 = 0;
            for (var h0 = 0; h0 <= Math.ceil(m / Y[r][0]); h0++) {
                var h3 = Math.ceil((m - h0 * Y[r][0]) / Y[r][3]);
                if (h3 < 0) h3 = 0;
                for (var w2 = 0; w2 <= Math.ceil(n / X[r][2]); w2++) {
                    var w3 = Math.ceil((n - w2 * X[r][2]) / X[r][3]);
                    if (w3 < 0) w3 = 0;
                    for (var h2 = 0; h2 <= Math.ceil(m / Y[r][2]); h2++) {
                        var h1 = Math.ceil((m - h2 * Y[r][2]) / Y[r][1]);
                        if (h1 < 0) h1 = 0;
                        var total = w0 * h0 + w1 * h1 + w2 * h2 + w3 * h3;
                        var X4 = n - w0 * X[r][0] - w2 * X[r][2];
                        var Y4 = m - h1 * Y[r][1] - h3 * Y[r][3];
                        if (X4 > 0 && Y4 > 0) {
                            total += simpleCover(X4, Y4, x, y);
                        } else {
                            X4 = n - w1 * X[r][1] - w3 * X[r][3];
                            Y4 = m - h0 * Y[r][0] - h2 * Y[r][2];
                            if (X4 > 0 && Y4 > 0) {
                                total += simpleCover(X4, Y4, x, y);
                            }
                        }
                        if (total == minimum) return minimum;
                        if (total < cover) cover = total;
                    }
                }
            }
        }
    }
    return cover;

    function simpleCover(n, m, x, y) {
        return Math.min(Math.ceil(n / x) * Math.ceil(m / y),
                        Math.ceil(n / y) * Math.ceil(m / x));
    }
}

document.write("(3, 3, 2, 2) &rarr; " + rectangleCover(3, 3, 2, 2) + "<br>");
document.write("(5, 6, 3, 2) &rarr; " + rectangleCover(5, 6, 3, 2) + "<br>");
document.write("(22, 18, 5, 3) &rarr; " + rectangleCover(22, 18, 5, 3) + "<br>");
document.write("(68, 68, 9, 8) &rarr; " + rectangleCover(68, 68, 9, 8) + "<br>");
document.write("(1109, 783, 170, 257) &rarr; " + rectangleCover(1109, 783, 170, 257) + "<br>");

更新：非最优和递归

确实有可能创建算法无法找到最佳解决方案的输入。对于示例 (218, 196, 7, 15)，它返回 408，但有一个包含 407 个矩形的解决方案。该方案的中心区域大小为22×14，可以被三个7×15的矩形覆盖；但是，该simpleCover函数仅检查所有矩形具有相同方向的选项，因此它只能找到中心区域有 4 个矩形的解决方案。

当然，这可以通过递归使用算法并rectangleCover再次调用中心区域来解决。为了避免无休止的递归，您应该限制递归深度，并simpleCover在达到一定的递归级别后使用。为了避免代码变得异常缓慢，请添加中间结果的记忆（但不要将在更深的递归级别中计算的结果用于更高的递归级别）。

当添加一级递归和中间结果记忆时，算法为上述示例找到了 407 的最优解，但当然需要更多时间。同样，我没有证据表明添加一定的递归深度（甚至无限的递归）将导致算法最优。