Dividing a set into two subsets the optimal way (May be similar to the knapsack problem) We have `n` stones having weight `m[1]..m[n]`, and two sacks. We put each stone into first or second sack; the resulting sacks weights with stones become `S[1]` and `S[2]` (the sacks themselves have no weight). The task is to divide stones so that the weight difference `|S[1] - S[2]|` is _minimal_ * * * Let me ask you if my approach is right: 1) let's sort the stones descending. 2) `i=1` 3) `A` is the index of the lightest sack (or first if they have equal weight) 4) put `m[i]` stone to `S[A]`, `S[A] += m[i]` 5) `i++` 6) if there are stones left `(i <= n)` then `goto 3`

This is an NP-hard optimization variant of the PARTITION problem which is NP-complete (for deciding if it's possible to split them equally). The greedy algorithm you propose is a special case of an algorithm for scheduling with minimum makespan, and can be shown to be a 4/3 approximation for the problem of minimizing the max load on either element (which is the same as your problem for the purpose of computing the exact answer). However, there's a relatively simple dynamic programming solution that runs in pseudopolynomial time.