Code Fever
Updated Apr 8, 2011, 11:22 AM
Welcome folks to the world of learning..!
Use template
Other Algos‎ > ‎

Balanced Partition Problem




Problem Definition:

                                                You are given an array of n numbers, divide the numbers of this array into two sets such that the difference of their sum of both the subarrays is                                                        minimum.

                                                For Example:
                                                If the input is {1,2,3,5,10},
                                                then the output should be two arrays/sets such that the difference between their sums are minimum. So here the two such arrays are {1,2,3,5} , {10},                                                    here sum of the first array is 11 , and sum of the second array is 10. Hence, their difference 11-10 = 1 is minimum possible.

                                                This problem will always timeout if you try to generate every possible subset of the array to generate two partitions.

                                                Here is the nice solution to this problem,

                                               

Source Code with Explanation

First, we split our array in half and get two arrays L[n/2] and R[n-n/2]. For each of these arrays we iterate through all its subsets (including the empty one) and calculate their sums. So, we get two arrays SumL[2^(n/2)] and SumR[2^(n-n/2)]. Then we sort these arrays. The preparation is over. We got two arrays with sums. Now we are going to maintain two pointers PL that will go through the SumsL from left to right, and PR that will go through the SumsR from right to left. Initially we set result to -INFINITY. At each moment in time the following will be true: either our result equals to C already, or there exist such X and Y that we can get C as a sum of SumsL[X] + SumsR[Y] and X >= PL and Y <= PR. To maintain this invariant it is sufficient at each step to move PL to the right or PR to the left according to the current sum SumL[PL]+SumR[PR]. The proof is not hard, so we left it to the reader. C++ code follows:

Given: vector<int> A;

    Lsz = 1 << n/2;    // size of sumL
    Rsz = 1 << (n - n/2);    //size of sumR

    for( int i = 0 ; i < Lsz ; i++){
            long long temp = 0;
            for( int j = 0 ; j < A.size()/2 ; j++){
                    if( (i & (1 << j)) > 0 )
                            temp +=  A[j];
            }
            sumL[i] = temp;
    }
   
    for(int i = 0 ; i < Rsz ; i++){
            long long temp = 0;
            for(int j = 0 ; j < n-n/2 ; j++){
                    if( (i&(1<<j)) > 0 )
                            temp += A[j + n/2];
            }
            sumR[i] = temp;
    }
   
    sort( sumL , sumL+Lsz );
    sort( sumR , sumR+Rsz );
   
    int totalSum = 0;

    for(int i = 0 ; i < n ; i++)
            totalSum += A[i];

    int cur = INT_MIN;
    int PL=0,PR=Rsz-1;

    while(PL < Lsz && PR >= 0){
            if(2*(sumL[PL]+sumR[PR]) <= totalSum){
                    cur = max( cur , sumL[PL]+sum[PR]);
                    ++PL;
            }

            else --PR;
    }

now, at the end "cur" will contain the sum of one of the required partitions.
So, the answer would be two partition of sum: {cur,totalSum-cur}

This meet-in-the-middle algorithm is not something new in the programming competitions. From time to time it comes up. Here is a small tip: if you encounter an array with its size close to 40, consider splitting it in half and using the aforementioned technique.

Try these problems also:    ArithmeticalMean, KnapsackProblem.


Solution Using Dynamic Programming:

Source Code

int BalancedPartition ( int a[] , int n ){

    int sum = 0;
    for( int i = 0 ; i < n ; i++)
        sum += a[i];

    int *s = new int[sum+1];

    s[0] = 1;
    for(int i = 1 ; i < sum+1 ; i++)    s[i] = 0;

    int diff = INT_MAX , ans;

    for(int i = 0 ; i < n ; i++)
    {
        for(int j = sum ; j >= a[i] ; j--)
        {
            s[j] = s[j] | s[j-a[i]];
            if( s[j] == 1 )
            {
                if( diff > abs( sum/2 - j) )
                {
                    diff = abs( sum/2 - j );
                    ans = j;
                }

            }
        }
    }
    cout<< ans << " " << sum-ans<< endl; //two balanced partitions

    return min( ans , sum-ans );
}




Comments