魔方吧·中文魔方俱乐部

标题: 【优化】箱子装货物（圆木）的问题 [打印本页]

作者: migl 时间: 2009-5-27 11:16:59 标题: 【优化】箱子装货物（圆木）的问题

不知道吧里有没有类似问题。这个问题实在是不知道如何去搜索，干脆直接问了。
相信能在这里找到答案。感觉应该有现成的理论成果。
如果觉得题中的“圆木”不好理解，则可以变通为刚出笼的包子、馒头之类~~

如图所示。
第一个图的箱子里的圆木是正方形排布，装了32根。
第二个图的箱子里的圆木是等边三角形排布，装了32根。
图一：

图二：

假设圆木半径是R，直径是D，则D=2R。
图示的箱子的内部尺寸是8D*4D，即刚好能如第一个图所示地齐刷刷装下8*4根圆木。
计算.GIF

计算第二个图，得到以下数据：
图示的圆木占用的宽度正好是4D，占用的长度是 R+4*[2*√(3)*R]+R=D+√(3)*4D＜D+1.75*4D=8D。即占用的长度比箱子的长度小。
所以这种等边三角形的排布也能保证32根圆木都能装进木箱。

从图示可以简单分析出一些“趣事”。
如果箱子内部尺寸是8D*3D，则：
图一能装24根圆木。（32-8）
图二能装23根圆木。（32-9）
图二少。
如果箱子内部尺寸是8D*5D：
图一能装40根圆木。（32+8）
图二能装41根圆木。（32+9）
图二多。
如果箱子内部尺寸是8D*6D：
图一能装48根圆木。（32+16）
图二能装50根圆木。（32+18）
图二更多。

很明显，内部尺寸越大，采用等边三角形排布的优势越大。

但是，同样是8*4的尺寸，如果是将长边铺满(8787)的话只能装30根，同比少2根。而且还空出一大块来，但就是塞不下(可以是8788)。
而同样是8*5的尺寸，如果是按照87878的话只能装38根，同比少2根。也是空出一块。
所以，将箱子内侧的哪条边铺满也有讲究。
而如果是9*4的尺寸，等边三角形排布(4343434344)也没有明显优势，只是有一点点空余。（蒸包子就不会粘在一起了。）

好了。本人的问题是：分界值是多少？
也就是说，当箱子的内部尺寸是几乘几时（正方形排布的尺寸），宜改用“等边三角形排布”，以提高空间的利用率。

再引申一下，还有没有更好的排布方法来提高空间的利用率？

附件: 44444444.GIF (2009-5-27 11:16:59, 13.79 KB) / 下载次数 26
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTIwODJ8ZDY4ODE1ODF8MTcxNTcwMzIwMnwwfDA%3D

附件: 434343434.gif (2009-5-27 11:16:59, 15.01 KB) / 下载次数 26
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTIwODN8ZDU5NGMwODF8MTcxNTcwMzIwMnwwfDA%3D

附件: 计算.GIF (2009-5-27 11:16:59, 13.57 KB) / 下载次数 23
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTIwODR8NzExMWJiNmN8MTcxNTcwMzIwMnwwfDA%3D

作者: migl 时间: 2009-5-27 11:59:59

难道这个比较难理解？

作者: noski 时间: 2009-5-27 12:02:35

对于长方体，宽为a，高为h（设D＝1）：
方案A（正方形排布）：
Na = [a] * [h]
方案B（沿着高h三角形排布）：
Nb = { m是奇数: m/2 * (2 * [h] - 1)
         m是偶数: (m - 1)/2 * (2 * [h] - 1) + [h]
                     }
方案C（沿着宽a三角形排布）：
Nc = { n是奇数: n/2 * (2 * [a] - 1)
         n是偶数: (n - 1)/2 * (2 * [a] - 1) + [a]
                     }
这里[]表示取整，m = [ 2 * (a - 1) / (√3) ] + 1，n = [ 2 * (h - 1) / (√3) ] + 1。
最后，圆木数：N = MAX{ Na, Nb, Nc }

作者: migl 时间: 2009-5-27 12:17:09

呵呵。
来了个高手。
编程，我是外行。
看了一下程序，好像是输入a、h这两个值后，经运算便得到N。

不知道这个N能否显示出是从哪个方案里出来的。
也许，直接列出这三个值更好。

作者: a306818142 时间: 2009-5-27 12:20:08

我数学不及格啊～看不懂

作者: noski 时间: 2009-5-27 12:23:42

嗯，要是找出这三个值最大的区域的边界，用不同的颜色画在一个坐标系中，x轴表示宽，y轴表示高，应该会挺漂亮的：）

作者: maqianxi 时间: 2009-5-27 12:38:03

这个问题~~~汗~~~~我还以为魔方类的呢

作者: lulijie 时间: 2009-5-27 13:55:35

这个题目有点意思，值得讨论。
若内部尺寸为8 * 3.95 （高为3.95或其他值，比4略小），原木直径为1，那么是不是可以放得下32根原木呢？
我认为应该可以放得下。这需要计算。
这种情况的放法就不能采用Noski兄的那三种方案。
试想一下楼主第二图的方法，底面上（即宽度上）尚有缝隙，在重力的作用下，必然使每个偶数列上的3根原木下降高度，箱子两边的原木紧贴箱壁，奇数列最上面的原木往侧边滚下，总高度必然下降。达到平衡状态。
------------------------------------------------------------------------
所以讨论本题目的一般情况，假设原木直径为1，箱子宽a和高h为实数（不仅仅为整数），放下最多原木的方案，不应该是Noski兄的那三种方案。

作者: noski 时间: 2009-5-27 14:12:40 标题: 回复 8# 的帖子

lulijie一针见血。。3楼的三种情况只是圆木挨着排列，的确不是最优的排列方法。当圆木之间的空隙在变化时，就不太好算了。。不过3楼的a和h是实数。
----------------------------
此时，再加入方案D和方案E，方案D表示“沿着高h三角形排布”这种情况，但此时的第一排靠墙的[h]个圆木要在整个长度上均匀分布，两头靠墙，中间空隙都相等（怎么这么不好描述-_-!）。方案E表示水平方向上这样带有一定间隙的排列。

这样对于方案D和E，计算公式与方案B、C相同，只要重新计算上述的m和n值就可以了。
（公式有点难看。。）
方案D：
球的列数m = [ (a - 1) / d1 ] + 1， d1表示相临两列球的球心的水平距离，d1 = √((2R)^2 - ((2R+Gap1)/2)^2 )，这里Gap1表示竖直第一列球的间隙，Gap1 = (h - [h]) / ( [h] - 1 )
方案E：
球的行数n = [ (h - 1) / d2 ] + 1，d2表示相临两行球的球心的垂直距离，d2 = √((2R)^2 - ((2R+Gap2)/2)^2 )，这里Gap2表示水平第一行球的间隙，Gap2 = (a - [a]) / ( [a] - 1 )

----------------------------
同时，如果出现这样的情况，比如高度为5.2，却不放5个球，而放4个球，球间隙为0.4，等等，就又需要其它的方案来计算了，需要把每行、列的球个数与Gap1当做变量，是可列举的。。

[ 本帖最后由 noski 于 2009-5-27 14:43 编辑 ]

作者: migl 时间: 2009-5-27 14:41:50

好像问题上升到微积分阶段了~~~

作者: lulijie 时间: 2009-5-27 15:50:17

下面一种方案：

假设箱子共装N层、M列原木。S表示总原木数。
那么高度h=(N-1)sinθ+1
   宽度a=(M-1)cosθ+1       θ在 30°到60°之间
M为偶数，S=M/2 * N=M*N/2
M为奇数，N为偶数，S=(M-1)/2 * N +N/2=M*N/2
M为奇数， N为奇数，  S=(M-1)/2 * N +(N+1)/2=(M*N+1)/2
即总原木数S=[(M*N+1)/2]    (  M*N为偶数S=M*N/2，M*N为奇数S=(M*N+1)/2  )
--------------------------------------------------------------------------------------------------
根据宽度a的值，及每个M值，M必须<2*a，求得θ值，再由高度公式求得最大的N值，这样就知道上述方案求得的S的最大值。（若把箱子转90度，就要把h和a的值交换后再计算。）
此外 θ小于 30°或大于60°时，就不能用上述方案，这里也有最大值，比较两种最大值，就知道最优方案。
θ小于 30°或大于60°时，具体是什么方案，我还没很好的思路。

附件: 111.JPG (2009-5-27 15:50:17, 19.75 KB) / 下载次数 17
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTIxMDl8NDYwYzJhMzZ8MTcxNTcwMzIwMnwwfDA%3D

作者: lulijie 时间: 2009-5-27 20:46:13

对于θ小于30°的情况：

a所在的层面为第一行，b所在的层面为第二行，c所在的层面为第三行。假设底层两个圆木的圆心之间的距离为2d。
则cosθ=d。
若θ小于30°，则d必须大于√3 /2。
则第二行对总高度无贡献。
三行的总高度为1+sin(60°+θ)=1+sin60°*cosθ+cos60°*sinθ
这样，三行中的任两行没有圆心在同一垂线上。
再往上叠加第四行，计算就越来越难了。

附件: 112.JPG (2009-5-27 20:46:13, 12.02 KB) / 下载次数 16
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTIxNDF8ZjhhYTE0NjN8MTcxNTcwMzIwMnwwfDA%3D

作者: kexin_xiao 时间: 2009-5-28 15:26:15

以前吧里好象有类似的题目

作者: migl 时间: 2009-6-1 15:23:11 标题: 回复 13# 的帖子

最好能看看前期的成果。

作者: xdgtzsyyj 时间: 2009-6-1 15:29:10

把大小不同的长方体物品装入箱子，看似简单，实际要装好的话，还很有难度

作者: migl 时间: 2009-6-1 16:11:36

圆形的，大小一致就够头痛了。
更不要说方的，还大小不一了。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)