作者singlovesong (~"~)
看板Prob_Solve
標題[問題] 20 個數字分三堆使得 最大的堆 為最小
時間Sat Jan 7 13:36:55 2012
如題
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
1F：推 springman:這好像是 NP-complete 的問題吧 01/07 20:44
2F：推 chchwy:看不太懂問題 最大的那堆和又最小 那到底是大還是小 01/07 22:50
3F：→ suhorng:@2f: minimize { max{sum1, sum2, sum3} } 01/08 00:15
4F：→ singlovesong:樓上所言甚是... 01/08 09:08
5F：→ singlovesong:應該不是NP-complete 因為這是比賽題 01/08 09:08
6F：推 springman:只是好像可以將 subset-sum 的問題 reduce 成這個問題 01/08 18:59
7F：→ springman:若沒想錯的話，應該是 NP-complete 沒錯 01/08 19:00