Divide a set of numbers into k subsets such that values are evenly distributed [duplicate]

This question already has an answer here: Closed 11 years ago.

Possible Duplicate:

equal k subsets algorithm

Say I've a set of numbers, I want to divide the numbers into k subsets such that the numbers are evenly distributed. By evenly distributed, I mean the sum of values in the subsets are closest to other sums of other subsets. Can we implement a DP solution to this 开发者_如何学JAVAproblem??

Please suggest!

---

All I can offer is my best attempt, here goes:

It seems to me that if m is the size of your set, then m/k = n; which is the number of elements in each set.

Now I am assuming you are working with integers, lets say we a set, s:

s ={1,2,3,4,5,6,7,8}

Now this is a simple idea that if you set is sorted then the sum of positions
-Sum(0 and last-0) = Sum(1,Last-1) = Sum(2,last-2) = Sum(3,last-3)... and so forth.

the variables would be:

• m = 8
• k = 2 (just for example)
• n = 4

so we want 4 sets: s1 = 1,8 = Sum is 9 s2 = 2,7 = Sum is 9 s3 = 3,6 = Sum is 9 s4 = 4,5 = Sum is 9

Now there will of course be some trickiness if the set size is odd and/or if k is odd, but these can be dealt with using special cases- implementing the situation that works best for your specific purpose.

Hope this gives you a push in the right, or pretty much any direction.