拔河比赛

拔河比赛：共t组数据，每组数据有N个人，他们的体重分别是W1-Wn，现要分成两组，两组人数差最多为1，体重差最小，求最小体重差的绝对值

对于这个题，首先分析一下如何体重差最小，其实就是体重越接近体重总和一半越好，所以上来先求体重和，把关键的判断部分弄清楚：

minw = min(abs(sum - w * 2),minw);

这里w就是第一组总重，这样我们就把问题简化成求一组总重了；

对于一组，参考背包问题，从头遍历来搜索，每个人都有在第一组和不在第一组两种情况，套深度搜索的格式：

void dfs(int y,int k,int w){   //k为当前取到人数， y为上一个人编号 ,w为总重 
    if(k == n / 2){
        minw = min(abs(sum - w * 2),minw);
        return;
    }
    if(y > n) return;
    dfs(y+1,k,w);
    dfs(y+1,k+1,w+a[y]); //取和不取，这是个问题，分两部分 
    
}

这里之前写时有一个误区，就是用for循环遍历，但是咱也不知道循环到的那位参赛者在不在组里，这样想分开讨论就很麻烦，所以优化如上

然后就是主程序段，按照题意设计即可。

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        sum = 0;
        for(int j = 1;j <= n;j++){
            scanf("%d",&a[j]);
            sum += a[j];
        }
        minw = 100000;
        dfs(1,0,0);
        printf("%d\n",minw);
    }
    return 0;
}

另外附易错位置：

minw预设要开大点

dfs（1，0，0）这里要注意开始的条件！编号从1开始，同时函数内要取等，还没取到人所以k为0.

然后就是每组数据读入前总重初始化为0

最后是总程序段：

#include
using namespace std;
int a[200],t,n;
int sum = 0,minw; 
void dfs(int y,int k,int w){   //k为当前取到人数， y为上一个人编号 ,w为总重 
    if(k == n / 2){
        minw = min(abs(sum - w * 2),minw);
        return;
    }
    if(y > n) return;
    dfs(y+1,k,w);
    dfs(y+1,k+1,w+a[y]); //取和不取，这是个问题，分两部分 
    
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        sum = 0;
        for(int j = 1;j <= n;j++){
            scanf("%d",&a[j]);
            sum += a[j];
        }
        minw = 100000;
        dfs(1,0,0);
        printf("%d\n",minw);
    }
    return 0;
}

总结：遇到新的题型不要慌，其实一些过程复杂的题都可以递归来做，这题抓住了题中人数最多差1的条件，有了n/2这个固定的边界条件，抓住这个突破口即可完成。