将一组数字分成两部分，其中差异最小

将一组数字（n个数字）划分为2个子集，以便子集1中的数字总和与子集2中的数字总和差异最小。同样，以下条件是必要的：将一组数字分成两部分，其中差异最小

如果n = 2K，每个子集具有k个成员
如果n = 2K + 1，一个子集具有k个成员，而另一个具有K + 1组的成员。

来源

2011-02-04 Kurosh

这听起来像一个家庭作业。 – 2011-02-04 21:31:46

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

（具有任意大小的分区分区问题等同于具有相同大小的分区问题 - 只需添加一个较大的值C到所有的数字和需求的差值小于C ...）

你也可能想看看http://en.wikipedia.org/wiki/Subset_sum_problem

来源

2011-02-05 01:51:10 hugomg

如果确保分割必须尽可能接近50/50的元素，您确定问题仍然是NP难吗？我的理解是，一般问题允许任意大小的分割。 – templatetypedef 2011-08-30 20:12:14

这个答案是从http://www.careercup.com/question?id=10244832复制

是NP-hard的本质，解决办法落入与复杂度为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）

来源

2014-10-05 05:02:18 georgechen

将一组数字分成两部分，其中差异最小

回答

相关问题