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

[問題] 20 個數字分三堆使得 最大的堆 為最小

看板Prob_Solve (計算數學 Problem Solving)作者 (~"~)時間13年前 (2012/01/07 13:36), 編輯推噓3(3推 0噓 4→)
留言7則, 4人參與, 最新討論串1/2 (看更多)
如題 input 20 個數字 1 <= 每個數字 <=200 要把這些數字分三堆使得最大的那堆的和為最小 請問這最小的和 為多少？ ex: N=6 1 2 3 4 5 6 1: 1 6 2: 2 5 3: 3 4 ans: 7 每堆的數量不限 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 58.114.85.48
推
01/07 20:44, , 1F
這好像是 NP-complete 的問題吧
01/07 20:44, 1F
推
01/07 22:50, , 2F
看不太懂問題 最大的那堆和又最小 那到底是大還是小
01/07 22:50, 2F
→
01/08 00:15, , 3F
@2f: minimize { max{sum1, sum2, sum3} }
01/08 00:15, 3F
→
01/08 09:08, , 4F
樓上所言甚是...
01/08 09:08, 4F
→
01/08 09:08, , 5F
應該不是NP-complete 因為這是比賽題
01/08 09:08, 5F
推
01/08 18:59, , 6F
只是好像可以將 subset-sum 的問題 reduce 成這個問題
01/08 18:59, 6F
→
01/08 19:00, , 7F
若沒想錯的話，應該是 NP-complete 沒錯
01/08 19:00, 7F
‣ 更多 singlovesong 的文章
文章代碼(AID): #1F1zdwP0 (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 singlovesong 的文章
文章代碼(AID): #1F1zdwP0 (Prob_Solve)