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

看板CSSE (電腦科學及軟體工程)作者 (JohnQ)時間14年前 (2010/08/27 21:10), 編輯推噓2(206)
留言8則, 4人參與, 最新討論串1/1
※ [本文轉錄自 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

08/27 22:54, , 1F
用一些局部最佳規則處理,就會得到相對最佳解了
08/27 22:54, 1F

08/28 23:59, , 2F

08/29 00:02, , 3F
這個問題是3D knapsack, 請看paper http://tiny.cc/eiqbc
08/29 00:02, 3F

08/29 18:57, , 4F
感謝各位提供的方式!
08/29 18:57, 4F

08/31 22:21, , 5F
這題只要把東西塞進包裝 不必最大化價值 不是knapsack
08/31 22:21, 5F

08/31 22:22, , 6F
但可以當作3D knapsack的一種特殊情況來看(每箱價值都為1)
08/31 22:22, 6F

08/31 22:24, , 7F
再看一次題目 要"總體積"最大 那確實是3D knapsack
08/31 22:24, 7F

08/31 22:24, , 8F
前面的推文弄錯了 sorry
08/31 22:24, 8F
文章代碼(AID): #1CTxbJWK (CSSE)
文章代碼(AID): #1CTxbJWK (CSSE)