[其他] 相對最佳值演算法的問題

[redskyism (JohnQ)]

※ [本文轉錄自 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個

   要塞進箱子中
   求能塞進的盒子總體積"相對"最大的演算法
   (所謂相對就是快速的求出一個好的解,不一定要是最佳解)

   請問有人知道這要怎麼去計算嗎?
   或者是告訴我有那個數學工具可以使用

   感謝!


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 175.180.237.185

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 175.180.237.185
→ yauhh:用一些局部最佳規則處理,就會得到相對最佳解了
推 Huangs:http://en.wikipedia.org/wiki/Packing_problem 3D packing
→ cobain:這個問題是3D knapsack, 請看paper http://tiny.cc/eiqbc
→ redskyism:感謝各位提供的方式!
推 Huangs:這題只要把東西塞進包裝  不必最大化價值  不是knapsack
→ Huangs:但可以當作3D knapsack的一種特殊情況來看(每箱價值都為1)
→ Huangs:再看一次題目 要"總體積"最大 那確實是3D knapsack
→ Huangs:前面的推文弄錯了 sorry