巧分矩形
本帖最后由 作者 于 2009-3-27 12:43:59 编辑 <br /><br /> <p>小时候看到的题。</p><p>一个长53宽32的矩形，要用它来切取长为7宽为5的小矩形，如何切取才能得到最多的小矩形？</p><p>下面这个切法当然是不行的，只切出40块！</p> <p>呵呵，原来我编过一个计算集装箱装箱量的程序，就是专门用来拼这样的东西的。</p><p>横放，则6行7列。为42。</p><p>下面余2，右边余4，这里有点问题，去掉1列为6*6。则右边4+7=11，可以放两列竖放的，可以放8个。</p><p>则合计为6*6+2*4=44个。</p><p></p><p></p> <p>帮明总截一下图。</p><p>42块的：</p><p></p><p></p><p>44块的：</p><p></p><p></p><p>但还不是最佳答案……</p> <p>对，还不是最优方案，差了在第一次排序时把最后一行重新计算一下竖排。</p> 46块了，还有更多的吗…… 本帖最后由 作者 于 2009-3-27 23:25:24 编辑 <br /><br /> <p>:)</p><p>两个47块的方案，应该还有一个最多48块方案的</p><p> </p><p> </p><p>不过找了许多47块的方案，还是发现不了48块的，有待高人指点了</p> <p>陈兄，高人也！</p><p>此类问题，有一般性的解决方法吗？！</p> <p>To ahlzl 卢老师</p><p>此题我是乱试的，这种应该只有数值算法吧，应该是很复杂的数学问题，因为还没有考虑块斜放啊等等问题。</p><p>如此题</p><p><a href="http://bbs.mjtd.com/forum.php?mod=viewthread&tid=73709">http://bbs.mjtd.com/forum.php?mod=viewthread&tid=73709</a></p><p>四楼中我提过几个网页，那里的也都是用计算机狂算得到的最优解，只有少数是得到证明的。</p><p>不过这种几何数值算法恐怕也是很难的。</p> <p>这个帖子我看过，强！</p><p>这个切分的题，是我小时候看到的，47是最佳结果！</p> <p>:)</p><p>我小时候也有类似的题一直疑惑着我，当时好像是看《中学生数理化》的</p><p>题目是100*100的盒子里能放多少个直径为1的棋子。</p><p>以前没有电脑，记得当时自己剪了100多个纸圆，不断的摆。</p><p>不过好像也没有找到答案。</p><p>呵呵，看来每个人心中总有一些儿时的梦想和追求~</p>
页:
[1]