Menu
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.
974
The array cannot be divided into 2 arrays of an equal sum.
A subarray is a contiguous part of array. An array that is inside another array. For example, consider the array [1, 2, 3, 4], There are 10 non-empty sub-arrays. The subarrays are (1), (2), (3), (4), (1,2), (2,3), (3,4), (1,2,3), (2,3,4) and (1,2,3,4).
You can't always split the array equally. Here in this array, you can't partition array into more than 2 subparts, otherwise it will give more than 3 parts as some of the elements are present there having sum more than the partitioned Sum.
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.
103
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
