将一组数字分成差值最小的两部分

Question

将一组数字（n 个数字）划分为 2 个子集，使得子集 1 中的数字之和与子集 2 中的数字之和相差最小。还需要满足以下条件：

• 如果 n = 2k，则每个子集有 k成员
• 如果 n = 2k+1，则一个子集有 k 个成员，另一个子集有 k+1 个成员。

Answer 1

这个问题是NP完全问题。 http://en.wikipedia.org/wiki/Partition_problem
您将不得不通过暴力找到解决方案。

（任意大小分区的分区问题相当于等大小分区的问题 - 只需将一个大值 C 添加到所有数字并要求差值小于 C...）

您可能还想看看http://en.wikipedia.org/wiki/Subset_sum_problem

Answer 2

此答案复制自http://www.careercup.com/question?id=10244832

由于本质上是 NP 困难，该解决方案属于复杂度为 O(n^2W) 的伪多项式时间算法，其中 n = 元素数，W = 元素之和。

//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;
    }
}

@hugomg提供的答案具有相同的时间复杂度，因为大值C至少应与W（=元素之和）一样大，从而使背包问题的时间复杂度 = O(n*(W + nW)) = O(n^2*W)