[其他] 相对最佳值算法的问题

楼主: redskyism (dreamer)   2010-08-27 21:10:41
※ [本文转录自 Math 看板 #1CTxVwZ- ]
作者: redskyism (JohnQ) 看板: Math
标题: [其他] 相对最佳值算法的问题
时间: Fri Aug 27 21:04:53 2010
在 长度 X,Y,Z 的箱子中,
若有 盒子 长度(X1,Y1,Z1) A1个
(X2,Y2,Z2) A2个
...
(Xn,Yn,Zn) An个
要塞进箱子中
求能塞进的盒子总体积"相对"最大的算法
(所谓相对就是快速的求出一个好的解,不一定要是最佳解)
请问有人知道这要怎么去计算吗?
或者是告诉我有那个数学工具可以使用
感谢!
作者: yauhh (小y宝贝)   2010-08-27 22:54:00
用一些局部最佳规则处理,就会得到相对最佳解了
作者: Huangs (我是大笨蛋)   2010-08-28 23:59:00
作者: cobain (笑哈哈)   2010-08-29 00:02:00
这个问题是3D knapsack, 请看paper http://tiny.cc/eiqbc
楼主: redskyism (dreamer)   2010-08-29 18:57:00
感谢各位提供的方式!
作者: Huangs (我是大笨蛋)   2010-08-31 22:21:00
这题只要把东西塞进包装 不必最大化价值 不是knapsack但可以当作3D knapsack的一种特殊情况来看(每箱价值都为1)再看一次题目 要"总体积"最大 那确实是3D knapsack前面的推文弄错了 sorry

Links booklink

Contact Us: admin [ a t ] ucptt.com