巧分矩形

ahlzl · 发表于 2009-3-27 12:43:00

本帖最后由作者于 2009-3-27 12:43:59 编辑

小时候看到的题。

一个长53宽32的矩形，要用它来切取长为7宽为5的小矩形，如何切取才能得到最多的小矩形？

下面这个切法当然是不行的，只切出40块！

mccad · 发表于 2009-3-27 21:41:00

呵呵，原来我编过一个计算集装箱装箱量的程序，就是专门用来拼这样的东西的。

横放，则6行7列。为42。

下面余2，右边余4，这里有点问题，去掉1列为6*6。则右边4+7=11，可以放两列竖放的，可以放8个。

则合计为6*6+2*4=44个。

ahlzl · 发表于 2009-3-27 21:54:00

帮明总截一下图。

42块的：

44块的：

但还不是最佳答案……

mccad · 发表于 2009-3-27 22:24:00

对，还不是最优方案，差了在第一次排序时把最后一行重新计算一下竖排。

ahlzl · 发表于 2009-3-27 22:37:00

46块了，还有更多的吗……

qjchen · 发表于 2009-3-27 23:05:00

本帖最后由作者于 2009-3-27 23:25:24 编辑

:)

两个47块的方案，应该还有一个最多48块方案的

不过找了许多47块的方案，还是发现不了48块的，有待高人指点了

ahlzl · 发表于 2009-3-27 23:11:00

陈兄，高人也！

此类问题，有一般性的解决方法吗？！

qjchen · 发表于 2009-3-27 23:30:00

To ahlzl 卢老师

此题我是乱试的，这种应该只有数值算法吧，应该是很复杂的数学问题，因为还没有考虑块斜放啊等等问题。

如此题

四楼中我提过几个网页，那里的也都是用计算机狂算得到的最优解，只有少数是得到证明的。

不过这种几何数值算法恐怕也是很难的。

ahlzl · 发表于 2009-3-27 23:35:00

这个帖子我看过，强！

这个切分的题，是我小时候看到的，47是最佳结果！

qjchen · 发表于 2009-3-28 09:17:00

:)

我小时候也有类似的题一直疑惑着我，当时好像是看《中学生数理化》的

题目是100*100的盒子里能放多少个直径为1的棋子。

以前没有电脑，记得当时自己剪了100多个纸圆，不断的摆。

不过好像也没有找到答案。

呵呵，看来每个人心中总有一些儿时的梦想和追求~

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