分数组可以认为是枚举子集问题
可以枚举出所有的子集，然后判读这个子集和他的补集是不是最小的哪一个
但是没有必要这么做，因为可以在枚举子集的过程中进行剪枝
下面是代码：代码中有详细的注释，里面有很多东西值得学习
while(cin>>s)
以及在DFS中每一条语句代表什么意义
排序对于枚举子集是很重要的，可以方便剪枝
//分数组，使用回溯法，枚举子集#include#include #include #include #include using namespace std;const int maxn = 100000;vector V;//合法则输出对应的正整数，不合法则0int string_int(string s){ int sum = 0; int pos = 0; while(pos < s.size()) { if(s[pos] <= '9' && s[pos] >= '0') { sum = sum * 10 + s[pos] - '0'; } else return 0; pos++; } return sum;}int ans[maxn];int best_ans[maxn];int SUM = 0;int min_gap;void print_V(){ for(int i = 0;i < V.size();i++) { printf("%d ",V[i]); } printf("\n");}void print_A(int cur){ for(int i = 0;i < cur;i++) { printf(" %d ",V[ans[i]]); } printf("\n");}bool DFS(int cur,int sum)//来看这个DFS中每一条语句的作用{//print_A(cur); //首先要明确，做一次选择，就像当于在解答树中添加了一条边。进入一次DFS，就是一个集合 //所以，是否要剪枝，应该在做选择的时候判断，这个当前的这个子集是什么情况需要在DFS一开始来判断 //注意只有枚举子集的解答树的答案可能在遍历的每一个结点上，像八皇后问题那样，可能的答案只能在最后的末端 if(SUM - sum - sum == 0) { min_gap = 0; memcpy(best_ans,ans,sizeof(int) * cur); return true;//找到了一个最优解，可以直接返回，所有的都可以不用再判断 } else if(SUM - sum - sum < min_gap) { min_gap = SUM - sum - sum; memcpy(best_ans,ans,sizeof(int) * cur); } int pos; if(cur == 0) { pos = 0; } else { pos = ans[cur - 1] + 1; } for(;pos < V.size();pos++) { //选择一次就相当于添加了一个分支 if(sum + V[pos] <= SUM / 2) { ans[cur] = pos; if(DFS(cur + 1,sum + V[pos]))//如果已经挑到了相等的，那么直接返回就可以了，如果递归后的地方有返回true的，那么在这个地方直接返回就可以了 return true; } else { return false;//因为后面的肯定比这个要大，所以选后面的没有意义 } } return false;}int main(){ freopen("input.txt","r",stdin); //scanf("%d",&x); string s; //cin>>s; int ok = 1; while(cin >> s)//重要 { int x = string_int(s); if(!x) { ok = 0; printf("EERROR\n"); break; } else { SUM = SUM + x; V.push_back(x); } } sort(V.begin(),V.end());//print_V(); min_gap = SUM; if(ok) { DFS(0,0); printf("%d %d",(SUM - min_gap) / 2,SUM - (SUM - min_gap) / 2 ); } return 0;}