最少要多少个正方形？

mahuan1279

当n=31,m=45时，最少需要多少个正方形？

mahuan1279

贪心算法得出的是10个，应该不是最少的个数。

qjchen

这种题属于矩形的正方形切分，应该是挺难的。搜索了一下，有些资料显示，求解此题的方法，似乎有贪心法（这个经常不是最优解），DP法（动态规划，按道理应该可以枚举出很好的结果的，但是有人举出了好些范例），而后又有人用的是暴力的方法，不过这个数值还不太大。上面这个只是目前简单搜索得到的一些结果。以后有时间可以继续查些结论出来。谢谢提供有趣题目。

根据暴力算法，以上这道31，45的最优解，似乎是9个，如下图。

chenjun_nj

qjchen 发表于 2020-5-18 22:34
这种题属于矩形的正方形切分，应该是挺难的。搜索了一下，有些资料显示，求解此题的方法，似乎有贪心法（这 ...

牛！！！！！！！！！！！

qjchen

谢谢chenjun兄，好久不见啊：）

上面这个也都是查来的而已，等以后有时间了可以来试试自己编程完成下。

记录一下前天搜索相关文献信息的过程。

我第一个搜索到的有用网页如下：

https://stackoverflow.com/questions/25903080/cut-rectangle-in-minimum-number-of-squares

其中，二楼给出了动态规划的C++代码，采用了记忆化的技巧

三楼告知了一个信息：贪心法和动态规划法可能都不是最优解，因为动态规划法对于13*11的问题，给出了答案8，而最优解其实是6

然后说 https://mathoverflow.net/questions/116382/tiling-a-rectangle-with-the-smallest-number-of-squares 这里给出了许多的DP反例
（注：此网页给出了比较专业的解答，没有太看懂，大致的意思是，当(n,m)互质的时候，其最优解是趋近于一个g(m)函数的。）

在第一个链接中，给出了另外一个网页
http://int-e.eu/~bf3/squares/，这个网页中给出了一个C++的代码。同时进行了解释一下。

认为通过暴力搜索的时候，其解可能有其下几种
Types of solutions
（1）Square：假如n=m的时候，其解就是1个方形解
If the rectangle is a square, then obviously one square is sufficient to fill it.

（2）Scaling：假如n和m非互质的时候，可以先进行互质后，把解进行缩放
If the two sides (n,m) of the rectangle have a common divisor d, then any solution for a rectangle of size (n/d,m/d) can be scaled up to a solution of size (n,m).

（3）切分：类似贪心法，先把大矩形切成一个方形+一个小矩形
Splitting
Another possible reduction is by splitting a rectangle of size (n,m) into two rectangles horizontally ((h,m) and (n-h,m)) or vertically ((n,v) and (n,m-v)).

（4）通用：这些方法不能用贪心法求解，其结果也是比较特殊的，进行专门的描述

Basic solutions
Sometimes none of the reductions mentioned yields an optimal solution. The smallest such case is (13,11).
注：在这种特别的解中，表达方法被称为Bouwkamp notation表达法
相关信息可见：https://everything2.com/title/Bouwkamp+code
所以，大家若运行下面这段代码，建议可以下载一个如 DEVCPP之类的简单IDE测试，可以得到切分的过程。目前这个程序建议m,n的数值已经逼近2000了。
http://int-e.eu/~bf3/squares/young.cc  （可以用DEVCPP运行）
http://int-e.eu/~bf3/squares/young-mt.cc  （多线程版本）
我个人运行的结果如下：


不过还有更简单的网页版本
http://int-e.eu/~bf3/squares/view.html#13,23


直接运行即可看到结果。

相似的信息也可参见wolfram的一些在线展示
https://demonstrations.wolfram.com/MinimallySquaredRectangles/
https://demonstrations.wolfram.com/PossibleCounterexamplesToTheMinimalSquaringConjecture/



其他相关网页：
http://www.squaring.net/sq/tws.html

最近一些比较新的研究论文
“Tiling a Rectangle with the Fewest Squares”：https://www.sciencedirect.com/science/article/pii/S0097316596901041?via%3Dihub

其他相关问题：

其实此问题应该是PACKING PROBLEM中的一个，（比如10*10的矩形中，可以放多少个直径为1的圆，10*10*10的立方体中，可以放多少个直径为1的球等等，都是这类问题，当数量到达一定程度的时候，问题近乎不可解，多数有一些暴力解，而且应该还有世界记录）
Packing Problem：https://en.wikipedia.org/wiki/Packing_problems




所以此类问题中，一类比较特殊的问题就是叫做完美正方形
https://mathworld.wolfram.com/PerfectSquareDissection.html
这类问题讨论如何将一个正方形分解为多个小正方形，也是很有趣的。



楼主最近另外一个帖子中的矩形排版问题，和这个问题有一些相近
Different rectangles in a rectangle
The problem of packing multiple rectangles of varying widths and heights in an enclosing rectangle of minimum area (but with no boundaries on the enclosing rectangle's width or height) has an important application in combining images into a single larger image. A web page that loads a single larger image often renders faster in the browser than the same page loading multiple small images, due to the overhead involved in requesting each image from the web server.
An example of a fast algorithm that packs rectangles of varying widths and heights into an enclosing rectangle of minimum area is here.

https://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu

mahuan1279

qjchen 发表于 2020-5-20 09:31
谢谢chenjun兄，好久不见啊：）

上面这个也都是查来的而已，等以后有时间了可以来试试自己编程完成下。
...

嗯，矩形排版就是这个意思，即如何选定一个最合适的矩形母板使得排版利用率最高。