Partition a set of numbers into two parts with the smallest difference

Partition a set of numbers (n numbers) into 2 subset s开发者_JAVA百科o that the sum of numbers in subset 1 has the least difference with the sum of numbers in subset 2. Also the following condition is necessary:

• If n = 2k, each subset has k members
• If n = 2k+1, one subset has k members and the other has k+1 members.

This problem is NP-complete. http://en.wikipedia.org/wiki/Partition_problem You will have to find solutions by brute-force.

(The Partition problem with partitions of arbitrary size is equivalent to the problem with equal size partitions - just add a large value C to all numbers and demand that the difference be less than C...)

You might also want to have a look at the http://en.wikipedia.org/wiki/Subset_sum_problem

This answer is copied from http://www.careercup.com/question?id=10244832

Being NP-hard by nature, the solution falls into pseudo-polynomial time algorithm with complexity O(n^2W) where n = # of elements, W = sum of elements.

//constraints: n is even
void fun (int items[], int n)
{
    int total = accumulate (items, items+n, 0) / 2;
    int maxSubsetSz = n/2 ;

    vector< vector<int> > T (maxSubsetSz+1, vector<int> (total+1, 0) );

    //T[i][j] is set if there exists subset of size i that sum up to j
    T[0][0] = 1;    

    for(int i = 0; i < n; i++) //consider taking i-th item      
       for(int k = maxSubsetSz-1; k >= 0; k--) //each item must be taken once, hence loop backwards
           for(int j = 0; j <= total-items[i]; j++)  
               if ( T[k][j] && items[i]+j <= total )                        
                     T [k+1] [j+items[i]] = 1;

    for(int j = total; j >= 1; j--)
       if ( T [maxSubsetSz][j] ) {
        cout << "sum : " << j << endl; 
        break;
    }
}

The answer provided by @hugomg has the same time complexity because the large value C should be at least as large as W (= sum of elements), thus make the time complexity of knapsack problem = O(n*(W + nW)) = O(n^2*W)