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

[dedicationsh (ddd)]

大意是說先給定兩個數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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.200.75
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1456376478.A.CD2.html
→ Caesar08: greedy是一種演算法，不是data structure
推 suhorng: 對答案m*做二分搜  greedy檢查是否能分每段不超過m*
→ Killercat: greddy就是指「當下最好組合」，不過通常來講
→ Killercat: greedy很難得到真正的最佳解
→ Killercat: 要搭配其他的方法才比較容易得到最佳解
推 KJFC: 從最小樹的二分搜到另一個數 讓他們的總和跟最大的數相差最
→ KJFC: 小。不知道這樣可不可以
→ KJFC: 最小數
→ KJFC: 恍神沒看到二樓解答