以最小平方数切割矩形

Question

我正在尝试解决以下问题:

将M*N的矩形纸张切割成正方形,使得:

1. 沿着与纸张的一侧平行的线切割纸张.
2. 切割纸张使得所得尺寸总是整数.

当纸张无法进一步切割时,该过程停止.

切割的纸张最小数量是多少都是正方形？

限制:1 <= N <= 100且1 <= M <= 100.

示例:设N = 1且M = 2,则答案为2,因为可以切割的最小平方数为2(纸张沿中间的较小边水平切割).

我的代码:

cin >> n >> m;

int N = min(n,m);
int M = max(n,m);
int ans = 0;

while (N != M) {
    ans++;
    int x = M - N;
    int y = N;
    M = max(x, y);
    N = min(x, y);
}

if (N == M && M != 0)
   ans++;

但我没有弄到这种方法有什么问题,因为它给了我一个错误的答案.

Answer 1

我认为DP和贪婪的解决方案都不是最优的.以下是DP解决方案的反例:

考虑尺寸为13 X 11的矩形.DP解决方案给出8作为答案.但最佳解决方案只有6个方格.

这个帖子有很多反例:https://mathoverflow.net/questions/116382/tiling-a-rectangle-with-the-smallest-number-of-squares

此外,请看看这个正确的解决方案:http://int-e.eu/~bf3/squares/

Answer 2

我把它写成一个动态(递归)程序.

编写一个试图在某个位置拆分矩形的函数.以递归方式为两个部分调用该函数.尝试所有可能的拆分,并采取最小结果的拆分.

基本情况是两边相等,即输入已经是正方形,在这种情况下结果是1.

function min_squares(m, n):

    // base case:
    if m == n: return 1

    // minimum number of squares if you split vertically:
    min_ver := min { min_squares(m, i) + min_squares(m, n-i)  |  i ? [1, n/2] }

    // minimum number of squares if you split horizontally:
    min_hor := min { min_squares(i, n) + min_squares(m-i, n)  |  i ? [1, m/2] }

    return min { min_hor, min_ver }

要提高性能,可以缓存递归结果:

function min_squares(m, n):

    // base case:
    if m == n: return 1

    // check if we already cached this
    if cache contains (m, n):
        return cache(m, n)

    // minimum number of squares if you split vertically:
    min_ver := min { min_squares(m, i) + min_squares(m, n-i)  |  i ? [1, n/2] }

    // minimum number of squares if you split horizontally:
    min_hor := min { min_squares(i, n) + min_squares(m-i, n)  |  i ? [1, m/2] }

    // put in cache and return
    result := min { min_hor, min_ver }
    cache(m, n) := result
    return result

在具体的C++实现中,您可以使用int cache[100][100]缓存数据结构,因为您的输入大小有限.将它作为静态局部变量,因此它将自动用零初始化.然后将0解释为"未缓存"(因为它不能是任何输入的结果).

可能的C++实现:http://ideone.com/HbiFOH

Answer 3

贪婪算法不是最优的.在6x5矩形上,它使用5x5正方形和5个1x1正方形.最佳解决方案使用2个3x3正方形和3个2x2正方形.

要获得最佳解决方案,请使用动态编程.蛮力递归解决方案尝试所有可能的水平和垂直第一次切割,以最佳方式递归切割两个部分.通过缓存(memoizing)每个输入的函数值,我们得到一个多项式时间动态程序(O(mn max(m,n))).