9

I came across this question and couldn't find a reasonable solution. How would you divide an unsorted integer array into 2 equal sized sub-arrays such that, difference between sub-array sums is minimum.

For example: given an integer array a[N] (unsorted), we want to split the array into be split into a1 and a2 where a1.length == a2.length i.e N/2 and (sum of all numbers in a1 - sum of all numbers in a2) should be minimum.

For the sake of simplicity, let's assume all numbers are positve but there might be repetitions.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
rplusg
  • 3,418
  • 6
  • 34
  • 49
  • is the original array sorted? LOL – जलजनक Jan 29 '13 at 17:27
  • @SparKot okay, i'm not aware of that detail. Lets say unsorted. – rplusg Jan 29 '13 at 17:31
  • 3
    Looks like you have pretty much the [partition problem](http://en.wikipedia.org/wiki/Partition_problem). Although not an exact dupe, it looks like the answers to [a previous question](http://stackoverflow.com/q/5717849/179910) probably apply here as well. – Jerry Coffin Jan 29 '13 at 17:36
  • Can someone write code for [Differencing Algo](http://en.wikipedia.org/wiki/Partition_problem#Differencing_algorithm)? – जलजनक Jan 29 '13 at 17:43
  • 1
    as @JerryCoffin said that it's **partition problem** with a simple modification. I can add that the modification would be on the matter of `a1.length == a2.length` and that can be solved with getting the minimum numbers from the largest array and putting them in the other one till having the condition satisfied. – mamdouh alramadan Jan 29 '13 at 19:04

1 Answers1

3

While others have mentioned that this is a case of the partition problem with modification, I'd like to point out, more specifically, that it is actually a special case of the minimum makespan problem with two machines. Namely, if you solve the two-machine makespan problem and obtain a value m, you obtain the minimum difference 2*m - sum(i : i in arr)

As the wikipedia article states, the problem is NP-complete for more than 2 machines. However, in your case, the List scheduling algorithm, which in general provides an approximate answer, is optimal and polynomial-time for the two-machine and three-machine case given a sorted list in non-increasing order.

For details, and some more theoretical results on this algorithm, see here.

Andrew Mao
  • 35,740
  • 23
  • 143
  • 224