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

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

难道这个比较难理解？

noski

对于长方体，宽为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

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

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

a306818142

我数学不及格啊～看不懂

noski

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

maqianxi

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

lulijie

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

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

migl

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