[问题] 整数分堆问题

楼主: dibery (简哥)   2016-07-31 23:12:03
现有 M 个正整数以及 N 个箱子
每个箱子的安全容量都是 S
限制是
1. 每个数字都必须丢进箱子里
2. 最小化 每一箱数字和超出 S 的和
输出
1. 每一箱需要装哪些数字才能符合条件
2. 每箱超出安全容量的和
任意最佳装法均可
例:有五个数字 60 60 60 50 45 及三个箱子,安全容量均为 100
最佳分法为
60 50 (超出10)
60 45 (超出5)
60
超出的和 = 10 + 5 = 15
作者: yr (Sooner Born Sooner Bred)   2016-07-31 23:37:00
那就 MIP 了,不过商用的 solver 很贵
作者: FRAXIS (喔喔)   2016-08-01 04:29:00
如果你一定要最佳解 大概就要搜寻法了..

Links booklink

Contact Us: admin [ a t ] ucptt.com