数据分组问题，ACM竞赛题
题目抽象出来是这样的：
给定一组数据如：33 35 40
将这组数据分成两个集团，使得两个集团中数据之和相差最小，输出最终两个集团中的数据之和
如例子中的这个分组应该为：33 40和35
即输出为：73 35
当然，给定的数据从3个到最大100000个之间

100分悬赏算法，无需代码

[解决办法]
动态规划问题（其实我也不太会），不过你这问题很典型，是标准的背包问题，
背包问题就是说现在有一个容量为s的背包，现在给你n个物品，其体积和价值分别为wi,vi，那么求在容量s内能获得的最大价值. 我们用d[i]数组来保存当背包容量为i时，背包的容纳最大价值，
那么我们有 d[s]=max(d[s-wi]+vi,d[s])， s是背包的一个子状态。
可以这么理解（本人理解），d[s-wi]相当于没有把物品i放进去是背包的价值，d[s]是容量为s时背包的最大价值，
现在把i放到d[s-wi]中去，使得背包容量为s,而价值为d[s-wi]+vi ,所以就不比较d[s-wi]+vi和d[s]，去他们的大值。
这个是我的想法，其实是有子状态的严格证明的，你可以找相关的资料看看
[解决办法]
0-1背包问题

C/C++ code

动态规划，0-1背包问题，weight[i]=value[i],Max_weight=Sum_weight/2[code=C/C++]#include <iostream>using namespace std;int Fbag(int n,int weight,int *w){    int a,b;    if(n==0)    {        if(weight>=w[0]) return w[0];        else return 0;    }    if(weight>=w[n])    {        a=Fbag(n-1,weight-w[n],w)+w[n];        b=Fbag(n-1,weight,w);        if(a>b) return a;        else return b;    }    return Fbag(n-1,weight,w);}int main(){    int n,sum_weight(0),bag_weight,fin_weight;    cin>>n;    int *arr=new int[n];    for(int i=0;i<n;++i)    {        cin>>arr[i];        sum_weight+=arr[i];    }    bag_weight=sum_weight/2;//最接近所有重量的一半为最优解    fin_weight=Fbag(n-1,bag_weight,arr);//最终一个背包的重量    cout<<"group A:"<<sum_weight-fin_weight<<endl;    cout<<"group B:"<<fin_weight<<endl;    return 0;}
[解决办法]
1. 任意分成两组，每组排序
2. 求两组和的差delta
3. 在和比较大的组里，选取最接近delta/2的数值x
4. 将x从和比较大的组移动到和比较小的组里
5. 重复第2步，直到delta为0或1，或者等于上次循环时求得的delta
[解决办法]
用动态规划做吧

给你写了个没优化过的

C/C++ code
#include "iostream"using namespace std;int dynamic_prog(int ary[], int n, int arv){    if (arv <= 0)        return 0;    if (n == 0)    {        if (abs(arv - ary[0]) < arv)            return ary[0];        return 0;    }     int L = dynamic_prog(ary, n - 1, arv - ary[n]);    if (abs(arv - ary[n]) <= abs(arv - (L + ary[n])))        return ary[n];    return ary[n] + L;}int main(){    int* ary = NULL;    int  arv = 0;    int  sum = 0;    int  num = 0;    cout<<"please input the count of the integer : ";    cin>>num;    if (num < 0)        return 1;    ary = new int[num];    for (int i = 0; i < num; ++i)    {        cout<<"integer "<<i<<" : ";        cin>>ary[i];        sum += ary[i];    }    arv = sum / 2;    int L = dynamic_prog(ary, num - 1, arv);    int R = sum - L;    cout<<L<<" "<<R<<endl;    delete[] ary;    return 0;}
[解决办法]
背包算法和贪心算法有局限性，不要到极限，比如有10000个数时程序就不行了。

52楼算法错误，因为那个要挑数的组中不见得就能有最佳的数。但改进还是有正确性的，
1，升序排序
2，分组，让左边数组和大于右边，求差的一半，再在左边挑数（一个或多个）最接近差的一半放到右边
（该方法再小的数多并且相邻数与数的差不大的时候可以得到最优解）

3，没小数并且相邻数数的差很大时，就要从左边挑出几个数的和与右边的几个数的和相差 最接近差的一半 的数组互换，应该就可得到最优解。