洛谷题单指南-搜索-P2392 kkksc03考前临时抱佛脚

原题链接：https://www.luogu.com.cn/problem/P2392

解题思路：参考https://www.cnblogs.com/jcwy/p/18003097

前面已经给出了二进制法的代码，这里给出DFS的代码

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 25;

int s1, s2, s3, s4;
int a[N], b[N], c[N], d[N];
int path[N];
int ans, maxx = INT_MIN, minx = INT_MAX; //ans是最终答案，tmp是计算每一科所需要的最少时间

//枚举所有的子集，计算子集和与剩余元素和之差的绝对值最小时，较大的那一组元素和
//所有path[i]=1的课程分为一组，所有path[i]=0的分为一组
void dfs(int e[N], int len, int k)
{
    if(k > len) //找到一个划分方法
    {
        int sum1 = 0, sum2 = 0; //sum1是path[i]=1的课程消耗时间之和，sum2是path[i]=0的课程消耗时间之和
        for(int i = 1; i <= len; i++)
        {
            if(path[i] == 1) sum1 += e[i];
        }
        sum2 = e[0] - sum1;
        if(abs(sum1 - sum2) < minx)
        {
            minx = abs(sum1 - sum2);
            maxx = max(sum1, sum2);
        }
        return;
    }

    path[k] = 0;
    dfs(e, len, k + 1);
    
    path[k] = 1;
    dfs(e, len, k + 1);
}

int main()
{
    cin >> s1 >> s2 >> s3 >> s4;
    for(int i = 1; i <= s1; i++) 
    {
        cin >> a[i];
        a[0] += a[i]; //a[0]是元素之和
    }
    for(int i = 1; i <= s2; i++) 
    {
        cin >> b[i];
        b[0] += b[i]; //b[0]是元素之和
    }
    for(int i = 1; i <= s3; i++) 
    {
        cin >> c[i];
        c[0] += c[i]; //c[0]是元素之和
    }
    for(int i = 1; i <= s4; i++) 
    {
        cin >> d[i];
        d[0] += d[i]; //d[0]是元素之和
    }
    
    dfs(a, s1, 1); 
    ans += maxx; maxx = INT_MIN; minx = INT_MAX;
    dfs(b, s2, 1); 
    ans += maxx; maxx = INT_MIN; minx = INT_MAX;
    dfs(c, s3, 1); 
    ans += maxx; maxx = INT_MIN; minx = INT_MAX;
    dfs(d, s4, 1); 
    ans += maxx;
    cout << ans;

    return 0;
}