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

[singlovesong (~"~)]

如題

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
推 springman:這好像是 NP-complete 的問題吧
推 chchwy:看不太懂問題 最大的那堆和又最小 那到底是大還是小
→ suhorng:@2f: minimize { max{sum1, sum2, sum3} }
→ singlovesong:樓上所言甚是...
→ singlovesong:應該不是NP-complete  因為這是比賽題
推 springman:只是好像可以將 subset-sum 的問題 reduce 成這個問題
→ springman:若沒想錯的話，應該是 NP-complete 沒錯