【优化】箱子装货物（圆木）的问题

migl

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

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

图二：


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

计算第二个图，得到以下数据：
图示的圆木占用的宽度正好是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)也没有明显优势，只是有一点点空余。（ 蒸包子就不会粘在一起了。 ）

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

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

migl

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

xdgtzsyyj

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

migl

最好能看看前期的成果。

kexin_xiao

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

lulijie

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

lulijie

下面一种方案：

假设箱子共装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°时，具体是什么方案，我还没很好的思路。

migl

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

noski

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 编辑 ]

lulijie

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