矩形分割的问题

wenfengbx · 发表于 2010-6-25 11:16

已知一个大矩形和一个小矩形，请问大矩形最多可以分割成多少个小矩形，如何计算。。。

luyuanhong · 发表于 2010-6-25 15:48

[这个贴子最后由luyuanhong在 2010/06/25 03:49pm 第 1 次编辑]

下面引用由wenfengbx在 2010/06/25 11:16am 发表的内容：
已知一个大矩形和一个小矩形，请问大矩形最多可以分割成多少个小矩形，如何计算。。。

楼主提出的问题说得不清楚。我猜想，可能是这样一个问题：

已知一个大矩形的长是 a ，宽是 b ；一个小矩形的长是 c ，宽是 d ( a≥b≥c≥d )。
现在要在大矩形内放置多个小矩形，放置时，要求小矩形的边与大矩形的边互相平行。
问：大矩形内最多可以放置多少个小矩形？如何计算？

技术员 · 发表于 2010-6-25 18:28

我记得有个贴有答案。

技术员 · 发表于 2010-6-25 20:26

有点像大园包小圆问题。这个像大方包小方啊。。

luyuanhong · 发表于 2010-6-28 06:18

[这个贴子最后由luyuanhong在 2010/06/28 06:20am 第 1 次编辑]

下面引用由luyuanhong在 2010/06/25 03:48pm 发表的内容：
楼主提出的问题说得不清楚。我猜想，可能是这样一个问题：
已知一个大矩形的长是 a ，宽是 b ；一个小矩形的长是 c ，宽是 d ( a≥b≥c≥d )。
现在要在大矩形内放置多个小矩形，放置时，要求小矩形的边与大矩形的边互相平行。
问：大矩形内最多可以放置多少个小矩形？如何计算？

我编写了一个软件，可以用多重循环搜索的方法求出这个问题的解。
下面就是一些用这个软件求得的解实际例子：

wangix · 发表于 2010-6-28 19:48

下面引用由luyuanhong在 2010/06/28 06:18am 发表的内容：
我编写了一个软件，可以用多重循环搜索的方法求出这个问题的解。
下面就是一些用这个软件求得的解实际例子：

能不能简单的讲一下你用的算法啊？

luyuanhong · 发表于 2010-6-28 21:03

[这个贴子最后由luyuanhong在 2010/06/28 09:06pm 第 2 次编辑]

下面引用由wangix在 2010/06/28 07:48pm 发表的内容：
能不能简单的讲一下你用的算法啊？

从我在第 5 楼中所举例的几个图可以看出：

每一种可能使小矩形数达到最多的放置，都可以分成图中黄、绿、蓝、灰那样的 4 块区域。
其中的某 1 块、2 块、3 块也可能不出现，相当于这一块的宽度为 0 或高度为 0 的情形。

我的多重循环搜索算法，先从黄色区域开始，让黄色区域的宽度和高度取遍各种可能的值。

在这两重循环中，每一步当黄色区域大小取定后，因为绿色区域要尽量填满黄色区域右边
的空隙，所以绿色区域的左右宽度可以确定，但是绿色区域的上下高度不确定，还可以取
各种不同的值。同时，因为蓝色区域要尽量填满黄色区域下边的空隙,所以蓝色区域的上下
高度也可以确定，但是蓝色区域的左右宽度不确定，还可以取各种不同的值。然后，再让
绿色区域的高度和蓝色区域的宽度取遍各种可能的值，这又是两重循环。循环中每一步当
绿色和蓝色区域的大小完全确定时，因为灰色区域要尽量填满右下方的空隙，所以灰色区
域的大小可以完全确定。就这样，通过四重循环，搜遍一切可能的最优放置方法。在循环
的每一步，都计算一下小矩形的个数，通过比较，就可以找出小矩形个数最多的放置方法。

wenfengbx · 发表于 2010-6-30 11:24

非常感谢解答，受益匪浅啊~~

		自动登录	找回密码
密码			注册

矩形分割的问题