题目大意
求最符合拔河比赛要求的分队方法。
题目分析
用一个三元组(x,y,z)来表示当前的情况:x为当前考虑到第几个人，y为当前已经选择了多少个人到第一个分队里，这队人的体重和为z。
当y==n/2或者x>n时结束。
用dfs暴搜来实现……
\(Code\)
#include<iostream>
#include<cstdio>
#include<cmath>
#define sco 50
using namespace std;
int T,n,s,ans,a[sco];
void dfs(int x,int y,int z){
if(y==n/2){
ans=min(ans,abs(s-z*2));
return;
}if(x>n) return;
dfs(x+1,y+1,z+a[x]);
dfs(x+1,y,z);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);s=0;
for(int i=1;i<=n;++i){
scanf("%d",a+i);s+=a[i];
}
ans=2e9;
dfs(1,0,0);
printf("%d\n",ans);
}
return 0;
}