第十一届蓝桥杯c++A组第三题

方法一:dfs

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

LL res = 0x3f3f3f3f;     //一个无限大的数

int a[20];

void dfs(int n,LL s1,LL s2)
{
    if(n == 15)
    {
        res = min(res,abs(s1-s2));
        return ;
    }

    dfs(n+1,s1+a[n],s2);
    dfs(n+1,s1,s2+a[n]);
}

int main()
{
    for(int i = 0;i < 15;i++) cin>>a[i];
    sort(a,a+15);
    dfs(0,0,0);
    cout<<res;
    return 0;
}

数据如下:

9090400
8499400
5926800
8547000
4958200
4422600
5751200
4175600
6309600
5865200
6604400
4635000
10663400
8087200
4554000