PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 整數分堆問題

看板Prob_Solve (計算數學 Problem Solving)作者dibery (簡哥)時間8年前 (2016/07/31 23:12)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串1/1

現有 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