→ yr: 那就 MIP 了，不過商用的 solver 很貴 07/31 23:37
推 FRAXIS: 如果你一定要最佳解 大概就要搜尋法了.. 08/01 04:29
現有 M 個正整數以及 N 個箱子
每個箱子的安全容量都是 S
限制是
1. 每個數字都必須丟進箱子裡
2. 最小化 每一箱數字和超出 S 的和
輸出
1. 每一箱需要裝哪些數字才能符合條件
2. 每箱超出安全容量的和
任意最佳裝法均可
例：有五個數字 60 60 60 50 45 及三個箱子，安全容量均為 100
最佳分法為
60 50 (超出10)
60 45 (超出5)
60
超出的和 = 10 + 5 = 15
---
只分成兩群的解法我有解過（也就是背包問題）
但目前我還不知道要怎麼推廣到更多群，用背包感覺陣列要加很多維
也有讀了一些 bin packing 相關的 heuristic （像是 first-fit、best-fit...）
但這又似乎不保證能得到最佳解
請問各位版大，有什麼關鍵字或想法可以提供嗎？謝謝
註：不是作業，也不是競賽題，而是我實際要用的
--
Ｔｈｉｓ ████ ███ ███◣ ████ ███◣ ◥◣ ◢◤
████ █ ████ ████ ████ ◣█◢
ｉｓ ████ █ ███▎ ████ ███◤ █ █
████ █ █████ ████ █◥◣ ██
ｄｉｂｅｒｙ ███◤ ███ ███◤ ████ ██◥◣ ███
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.184.18.198
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1469977927.A.B9E.html