作者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