这是著名的“集装箱问题”(Container Loading Problem或者称为Bin Packing Problem),又称为“三维背包问题”( 3-D Knapsack Problem) 众所周知一维的背包问题(0-1背包问题)可用动态规划解决 可惜的是二维三维的背包问题是NP完全问题 :-( 至今还没有找到多项式时间的算法,而且很可能根本没有多项式时间的算法 这类问题通常用近似算法或一些随机化算法 然而,最近的一些研究表明,不可能找到一个多项式时间的近似算法,使得该算法所得到的较优解与实际最优解的比值以一个常数为界;换句话说任何多项式时间的近似算法都无法保证与最优解近似的程度;(我记得这是上次听朱宏老师的讲座听到的,具体出自何处还有待考证) 另一种解决途径是随机化算法或遗传算法或神经网络,然而这些算法要么是不能保证得到最优解(也不能保证近似程度),要么是不能保证多项式时间的复杂度。所以这个问题是很难的,不要妄图找到最优解的算法了,还是考虑近似算法吧~下面的网站有一些相关资源: http://cs.ua.edu/reu/1998_stuff/German/index.html下面的论文提出了一种启发式搜索算法:A tree-search heuristic for the container loading problem, David Pisinger, Dept. of Computer Science, University of CopenhagenAbstract We consider the container loading problem where a number of rectangular boxes should be loaded into a container of fixed dimensions. In order to develop an effective heuristic, we restrict out problem to consider loadings which are guillotine cuttable, i.e. where the container may be filled by dividing it into layers and subdividing each layer into strips, a strip usually being a sequence of boxes. This restriction implies tha every strip may be optimally filled by solving a knapsack problem with capacity equal to the length of the strip. The depth of a layer as well as the thickness of each strip is decided through a branch-and-bound approach where at each node only a subset of branches is explored. Computational experiments involving up to 120 boxes are reported, showing tha several loading problems from the literature are solved to optimality in reasonable time, achieving an average filling of 91% of the container volume.这篇论文可以在http://cora.whizbang.com/ 搜索到 (搜索关键字“container loading”)我建议你看看这篇论文,该文所提出的算法也许对你有所帮助。 PS: 线性规划、整数规划、非线性规划等等统筹学中的规划算法都是指数时间复杂度的算法,这个问题的最大难度在于计算复杂度随着问题规模的增加而急剧的增加。与其用这些规划算法来解,还不如编程序搜索呢,只要剪枝得当,搜索的效率要比这些规划算法要高得多。PS又PS: 如果不一定要求最优解,而可以允许较优解的话,这个问题要简单的多。
>>但是决定这个问题的规模的并不仅仅是盒子的种类数目 我之所以这么说,是因为 Computational experiments involving up to 120 boxes are reported, showing tha several loading problems from the literature are solved to optimality in reasonable time, achieving an average filling of 91% of the container volume.注意到这里面只提到了一个 120 boxes,也就是说,这个算法可以对 120 boxes做很好的近似,而不管小盒子、大盒子体积的比例等因素。 如果只有 2 boxes的话,那么这个算法的速度,近似程度就会发生质变,甚至有可能出现最优解的“有效”算法。 再说,你凭什么认为决定这个问题的规模的并不仅仅是盒子的种类数目。虽然感觉上是这样,而我最初也是这么认为的。不过看了上面引用的这段论文而产生了前面的想法。
还给老师了。试着写个思路:
这道题实际就是求一个大盒怎样装二種小盒才最满的问题。
设可装入的小盒分别为x1,x2.
目标函数:min(z)=(100*50*50-(3*@*1)*x1-(5*4*3)*x2)
约束条件:x1 <=1000
x2 <=1000
3x1+5x2 <=100
2x1+4x2 <=50
x1_3x2 <=50
目标误差=min(3*2*1,5*4*3)
用松弛因子x3,x4,x5将上述约束变为等式,然后用“单纯型法”求解,
这个“单纯型法”有通用的算法程序,你找找看吧,不用自己编。
---------------------------------------------------------------
可能写得不对,但思路是绝对正确的,请懂这个的指正。
就按haiwer說的改成兩種小盒各10000個吧。
高手快支招呀!!!
都有这们课程,学数学的就更不用说了。恐怕无法在这里一下说得很清楚,
大意上用的是叠代算法,使松弛因子达到最小吧,因为加入松弛因子后,就变成。怎么求解多元方程组的问题了,怎么解,就是所谓的“单纯型法”。惭愧,都忘得差不多了,只能说这么多,要是按钮在就好了。还是找本运筹学的书看看吧。再找“单纯型法”的程序。前面写法有点儿毛病,应该是:
-----------------------------------------
目标函数:min(z)=(100*50*50-(3*2*1)*x1-(5*4*3)*x2)
约束条件:x1 <=10000
x2 <=10000
3x1+5x2 <=100
2x1+4x2 <=50
x1+3x2 <=50
X1*a_SingleWeight+X2*b_SingleWeight<=SumWeight
就可以了。所以这个条件也不好满足。若这两个前提不能满足,就不能用线性规划来逼近最优解。我自己考虑了一个思路,可以得出解,但不知道是不是最优解。我的思路是:
1、先在大盒(100*50*50)中放置A类盒(5*4*3),最多可以放
int(100/5)*int(50/4)*int(50/3)=20*12*16=3840
或 int(100/4)*int(50/3)*int(50/5)=25*16*10=4000
或 int(100/3)*int(50/4)*int(50/5)=33*12*10=3940
最大值为4000,所以按第二种方法放置。2、第一步完成后,大盒中会产生一个未被占用的空间,可以知道规格是100*2*50。用第一步中的方法,可以知道最多可以在其中放1650个B类盒(3*2*1)。3、10000=2*4000+2000
10000=2*1650+6700
所以按前两步的放置方法可以放两个盒子,最后还余下2000个A类盒和6700个B类盒。继续前两步的方法,判断需要几个盒子。结论是一个盒子可以放得下。所以最后答案是需要三个盒子。现在关键问题是我不知道这样得到的是不是最优解。因为我的前提是同一种盒子在一个空间中摆放方向都是一样的,这样是不是比摆放方向不一样能放进更多的盒子,我不知道怎么用数学方法来证明它正确或者错误。严格意义上是需证明才能有说服力。
好多年前我就想过这个问题了。 用在如: "装货柜" 前计算体积之类的功能上.
HE HE ~ 好难啊 ! 让我来 UP ------
我这里有一个其他的运筹软件,你要的话我可以发给你。
我劝你不要想怎么做了,因为这个东西是别人软件的一个功能模块
众所周知一维的背包问题(0-1背包问题)可用动态规划解决
可惜的是二维三维的背包问题是NP完全问题 :-(
至今还没有找到多项式时间的算法,而且很可能根本没有多项式时间的算法
这类问题通常用近似算法或一些随机化算法
然而,最近的一些研究表明,不可能找到一个多项式时间的近似算法,使得该算法所得到的较优解与实际最优解的比值以一个常数为界;换句话说任何多项式时间的近似算法都无法保证与最优解近似的程度;(我记得这是上次听朱宏老师的讲座听到的,具体出自何处还有待考证)
另一种解决途径是随机化算法或遗传算法或神经网络,然而这些算法要么是不能保证得到最优解(也不能保证近似程度),要么是不能保证多项式时间的复杂度。所以这个问题是很难的,不要妄图找到最优解的算法了,还是考虑近似算法吧~下面的网站有一些相关资源:
http://cs.ua.edu/reu/1998_stuff/German/index.html下面的论文提出了一种启发式搜索算法:A tree-search heuristic for the container loading problem, David Pisinger, Dept. of Computer Science, University of CopenhagenAbstract
We consider the container loading problem where a number of rectangular boxes should be loaded into a container of fixed dimensions. In order to develop an effective heuristic, we restrict out problem to consider loadings which are guillotine cuttable, i.e. where the container may be filled by dividing it into layers and subdividing each layer into strips, a strip usually being a sequence of boxes. This restriction implies tha every strip may be optimally filled by solving a knapsack problem with capacity equal to the length of the strip. The depth of a layer as well as the thickness of each strip is decided through a branch-and-bound approach where at each node only a subset of branches is explored.
Computational experiments involving up to 120 boxes are reported, showing tha several loading problems from the literature are solved to optimality in reasonable time, achieving an average filling of 91% of the container volume.这篇论文可以在http://cora.whizbang.com/ 搜索到 (搜索关键字“container loading”)我建议你看看这篇论文,该文所提出的算法也许对你有所帮助。
PS: 线性规划、整数规划、非线性规划等等统筹学中的规划算法都是指数时间复杂度的算法,这个问题的最大难度在于计算复杂度随着问题规模的增加而急剧的增加。与其用这些规划算法来解,还不如编程序搜索呢,只要剪枝得当,搜索的效率要比这些规划算法要高得多。PS又PS:
如果不一定要求最优解,而可以允许较优解的话,这个问题要简单的多。
这个问题有它的特殊性,就是只有两种box。不要因为是NP就认为解不出,举个例子,如果Hamilton路只有2个点,怎么做都做得出。另外,这个问题中大多数据都已经指明,应该可以找出好的,有针对性的算法(不要看我,我可找不出)。
我们是货运公司,上头想找一个优化集装箱、货柜的方法,我觉得麻烦一句“做不了”就推了——呵呵,的确作不了。
我以为顶楼的兄弟所提出的数据只是一个用来说明问题的例子
他的实际应用中应该不会只有两种盒子
退一步,就算只有两种盒子
这个问题还是很难解
你所举的哈密尔顿回路的例子并不恰当
因为哈密尔顿回路问题中图的顶点数就唯一地确定了问题的规模
但是决定这个问题的规模的并不仅仅是盒子的种类数目
而是与盒子本身的数目,以及小盒子、大盒子体积的比例等因素有关
如果盒子本身的数目很大的话(比如只有两种小盒子,但是每种都有100万个)
这个问题还是很难解的不过,我所提到的那篇论文中的搜索算法还是挺不错的,可能在实际应用中有一定的价值
我之所以这么说,是因为
Computational experiments involving up to 120 boxes are reported, showing tha several loading problems from the literature are solved to optimality in reasonable time, achieving an average filling of 91% of the container volume.注意到这里面只提到了一个 120 boxes,也就是说,这个算法可以对 120 boxes做很好的近似,而不管小盒子、大盒子体积的比例等因素。
如果只有 2 boxes的话,那么这个算法的速度,近似程度就会发生质变,甚至有可能出现最优解的“有效”算法。
再说,你凭什么认为决定这个问题的规模的并不仅仅是盒子的种类数目。虽然感觉上是这样,而我最初也是这么认为的。不过看了上面引用的这段论文而产生了前面的想法。