数据分组问题，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背包问题
动态规划，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
[解决办法]
用动态规划做吧
给你写了个没优化过的
#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，没小数并且相邻数数的差很大时，就要从左边挑出几个数的和与右边的几个数的和相差 最接近差的一半 的数组互换，应该就可得到最优解。