Partitioning a list of integers to minimize differ

问题:

Given a list of integers l, how can I partition it into 2 lists a and b such that d(a,b) = abs(sum(a) - sum(b)) is minimum. I know the problem is NP-complete, so I am looking for a pseudo-polynomial time algorithm i.e. O(c*n) where c = sum(l map abs). I looked at Wikipedia but the algorithm there is to partition it into exact halves which is a special case of what I am looking for...

EDIT: To clarify, I am looking for the exact partitions a and b and not just the resulting minimum difference d(a, b)

To generalize, what is a pseudo-polynomial time algorithm to partition a list of n numbers into k groups g1, g2 ...gk such that (max(S) - min(S)).abs is as small as possible where S = [sum(g1), sum(g2), ... sum(gk)]

回答1:

A naive, trivial and still pseudo-polynomial solution would be to use the existing solution to subset-sum, and repeat for sum(array)/2to 0 (and return the first one found).

Complexity of this solution will be O(W^2*n) where W is the sum of the array.

pseudo code:

for cand from sum(array)/2 to 0 descending:
   subset <- subsetSumSolver(array,cand)
   if subset != null:
        return subset

The above will return the maximal subset that is lower/equals sum(array)/2, and the other part is the complement for the returned subset.

---

However, the dynamic programming for subset-sum should be enough.

Recall that the formula is:

f(0,i) = true
f(x,0) = false | x != 0
f(x,i) = f(x-arr[i],i-1) OR f(x,i-1)

When building the matrix, the above actually creates you each row with value lower than the initial x, if you input sum(array)/2 - it's basically all values.

After you generate the DP matrix, just find the maximal value of x such that f(x,n)=true, and this is the best partition you can get.

Complexity in this case is O(Wn)

回答2:

You can phrase this as a 0/1 integer linear programming optimization problem. Let wi be the ith number, and let xi be a 0/1 variable which indicates whether wi is in the first set or not. Then you want to minimize sum(xi wi) - sum((1 - xi) wi) subject to

sum(xi wi) >= sum((1 - xi) wi)

and also subject to all xi being 0 or 1. There has been a lot of research into optimizing 0/1 linear programming solvers. For large total sum W this may be an improvement over the O(W n) pseudo-polynomial time algorithm presented because the W factor is scary.

回答3:

My first thought is to:

1. Sort list of integers
2. Create two empty lists A and B
3. While iterating from biggest integer to smallest integer...add next integer to the list with the smallest current sum.

This is, of course, not guaranteed to give you the best result but you can bound the result it will give you by the size of the biggest integer in your list