f*********d 发帖数: 140 | 1 有2*N个文件,文件的大小保存在size[2*N]中。然后想要分成N份(每一份可以有1或者
多个文件),要使这N份中的文件size之和的最大值最小,如果实现?
题目来之MS |
z****e 发帖数: 54598 | 2 sort一遍
从大往小排n个
然后剩下n个,从大往小,尽量塞到高度最小的文件中去 |
f*********d 发帖数: 140 | 3 多谢大牛指点, 但是这个应该是近似解~
不过要是能给出个近似比,那面试的时候也可以免死了 哈哈~
【在 z****e 的大作中提到】 : sort一遍 : 从大往小排n个 : 然后剩下n个,从大往小,尽量塞到高度最小的文件中去
|
e*******8 发帖数: 94 | 4 这个就是minimum makespan scheduling. vazirani的那本书上就有一个挺简单的2-
approximation algorithm和一个复杂点的PTAS |
f*********d 发帖数: 140 | 5 鞠躬致敬~
【在 e*******8 的大作中提到】 : 这个就是minimum makespan scheduling. vazirani的那本书上就有一个挺简单的2- : approximation algorithm和一个复杂点的PTAS
|