Split $\{1,2,...,n\}$ into $k$ subsets so that the sum of the elements in each subset are as close as possible.

37 Views Asked by At

Let $S_i,i=1,...,k$ to be the sum of elements in subset $k$, I want to minimize $\max_i S_i - \min_i S_i$. I have thought about some greedy method but they are not optimal. I know that partition problem is NPC. I wonder if my problem is NP-hard or can be solved in polynomial time. Thanks for any help!