一个一维数组，选择一部分元素，它们可以分成和相等的两堆，求方法 - C语言论坛

楼主

已结贴√ 问题点数：20 回复次数：3

一个一维数组，选择一部分元素，它们可以分成和相等的两堆，求方法

一个一维整型数组，取出一部分元素，这些元素恰好可以分成和相等的两堆，求不同和的个数。其中数组元素个数小于15。求大佬们提供一个思路。

搜索更多相关主题的帖子: 维数　选择　元素　相等　方法　

第 2 楼

得分:10

程序代码：

#include <iostream>  
#include <vector>  
#include <numeric>  
using namespace std;  
struct Node  
{  
    bool reach;  
    int parent;   
    int value;  
      
    Node(): reach( false ), parent( 0 ), value( 0 )  
    {  
    }  
};  
int main()  
{  
    vector<int> seq;  
    for( int i; (cin >> i) && i; ) seq.push_back( i );  
      
    int allsum = accumulate( seq.begin(), seq.end(), 0 );  
    int partsum = allsum / 2;  
      
    vector<Node> f( partsum + 1 );  
    f[0].reach = true;  
    int rmpos = 0;  
      
    for( vector<int>::iterator it = seq.begin(); it != seq.end(); it++ )  
    {  
        bool rm = true;  
        for( int i = min(rmpos, partsum - *it); i >= 0; i-- )  
        {  
            if( !f[i].reach ) continue;  
            Node& next = f[i + *it];  
            next.reach = true;  
            if( !next.parent )  
            {  
                next.parent = i;  
                next.value = *it;  
            }  
            if( rm )  
            {  
                rmpos = max( rmpos, i + *it );  
                rm = false;  
            }  
        }  
    }  
      
    while( !f[partsum].reach ) partsum--;  
    cout << "The minimum difference of sums of two parts is " << allsum - partsum * 2 << endl;  
    cout << "The smaller part is: ";  
    for( int p = partsum; p != 0; p = f[p].parent ) cout << f[p].value << " ";  
    cout << endl;  
    return 0;  
}