[討論] UVA 練習題 二分法和greedy

作者: dedicationsh (ddd)   2016-02-25 13:01:11
大意是說先給定兩個數m和k,
m表示資料個數,k表示將m個資料分為k份
找出最好的分法,使得max(每份的總和)有最小值
Sample Input
2 //總共兩組數據
9 3 //9份資料 分3等份
100 200 300 400 500 600 700 800 900
5 4 //5份資料 分4等份
100 100 100 100 100
Sample Output
100 200 300 400 500 / 600 700 / 800 900
100 / 100 / 100 / 100 100
請問大家有什麼想法嗎
網路上是說用二分法和greedy
我不太清楚二分法是要用來找什麼
greedy我不清楚他的意思,沒修過data structure
附上連結:http://www.cnblogs.com/huaszjh/p/4705130.html
作者: Caesar08 (Caesar)   2016-02-25 13:45:00
greedy是一種演算法,不是data structure
作者: suhorng ( )   2016-02-25 14:59:00
對答案m*做二分搜 greedy檢查是否能分每段不超過m*
作者: Killercat (殺人貓™)   2016-02-27 12:05:00
greddy就是指「當下最好組合」,不過通常來講greedy很難得到真正的最佳解要搭配其他的方法才比較容易得到最佳解
作者: KJFC (磁鐵貓)   2016-03-02 08:29:00
從最小樹的二分搜到另一個數 讓他們的總和跟最大的數相差最小。不知道這樣可不可以最小數恍神沒看到二樓解答

Links booklink

Contact Us: admin [ a t ] ucptt.com