第二题

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <bitset>
#include <algorithm>
#include <limits>
#include <functional>
using namespace std;

bool sto_vec(const string &str,vector<int>& vec){//把数组分离出来
	int count =0;
	for(int i(0);i<str.size();++i){
		if(str[i]>='0' && str[i]<= '9')
			count++;
		else if(str[i] == ' ' && count !=0){
			vec.push_back(stoi(str.substr(i-count,count)));
			count=0;
		}else
			return false;

	}
	if(count>0)
		vec.push_back(stoi(str.substr(str.size()-count,count)));
	return true;
}


//方法一：时间复杂度2^n，需要减枝
int dp_func(int i,int j,const vector<int>& vec){ //递归模拟动态规划0-1背包,j为代价,时间复杂度太大，舍去；
	if(i==0 || j==0) return 0;
	auto temp (dp_func(i-1,j,vec));//先算不取这个值的，成功可能性大
	if(j<vec[i] || temp == j){
		return temp;
	}else{
		return max(temp,dp_func(i-1,j-vec[i],vec)+vec[i]);
	}
}

//方法二：时间复杂度2^n，需要减枝
void dfs(int i,const int& half,int now_sum,const vector<int>& vec,int& ans){
	if(i==vec.size()) return;
	auto temp(now_sum+vec[i]);
	if(temp == half){
		ans =half;
		return;
	}else if(temp<half){
		ans = max(ans,temp);
		dfs(i+1,half,temp,vec,ans);//选中
		if(ans == half)return;
	}
	//不选中
	dfs(i+1,half,now_sum,vec,ans);
	return ;
}

//方法三，参考大神们的；时间复杂度2^(n/2)。运行时间：40ms
//思想：把数组分成左右两半，左边（长度left）各种元素相加可能性有2^left种；右边有2^righ种；
//然后寻找所有可能性中，左边部分+右边部分小于等于half的最大值；
//我这儿为了思路清晰，把大神的许多优化去掉了
int solve(const vector<int>& vec,const int& half){
	int len(vec.size());
	int left(len/2);
	int right(len-left);
	int left_status(1<<left);//2^left
	int right_status(1<<right);

	bitset<32> assist; 
	vector<int>left_sum;//左半各种相加的可能性
	for(int i(0);i<left_status;++i){
		assist=i;
		int temp =0;
		for(int j(0);j<left;++j){
			if(assist[j]){
				temp += vec[j];
			}
		}
		if(temp<=half){
			left_sum.push_back(temp);
		}
	}
	sort(left_sum.begin(),left_sum.end());

	vector<int>right_sum;//右半各种相加的可能性
	for(int i(0);i<right_status;++i){
		assist=i;
		int temp =0;
		for(int j(0);j<right;++j){
			if(assist[j]){
				temp += vec[j+left];
			}
		}
		if(temp<=half){
			right_sum.push_back(temp);
		}
	}

	//寻找左+右小于等于half且最接近half
	int ans(numeric_limits<int>::min());
	for(const auto& item:right_sum){
		auto iter = upper_bound(left_sum.begin(), left_sum.end(), half - item);//*iter为left_sum中满足*iter>half - item的第一个值，既满足item + *(--iter)<=half的最大值；
		if (iter != left_sum.begin()){
			--iter;
			ans = max(ans, item + *iter);
		}
	}
	return ans;
}

int main(){
	string str;
	int ans;
	while(getline(cin,str) && !str.empty()){
		vector<int> vec;
		if(!sto_vec(str,vec)){
			cout<<"ERROR"<<endl;
			continue;
		}
		int sum = accumulate(vec.begin(),vec.end(),0);
		int half = sum/2;

		//大的排前面能大大优化性能。对方法一、运行时间：185ms；小的排前为516ms。
		//对方法二：运行时间：89ms；小的在前运行时间：238ms。
		//对方法三：运行时间：35ms；小的在前运行时间：32ms，相差不大，小的在前貌似更优
		//sort(vec.begin(),vec.end(),greater<int>());//方法一、二使用
		//sort(vec.begin(),vec.end());//方法三使用

		//方法一，递归模拟动态规划0-1背包，时间复杂度太大,运行时间：317ms
		//sort(vec.begin(),vec.end(),greater<int>());
		//vec.insert(vec.begin(),0);//第一个元素为0，占位，为了序号从1开始，不从0开始;
		//ans = dp_func(vec.size()-1,half,vec);

		//方法二
		//sort(vec.begin(),vec.end(),greater<int>());
		//dfs(0,half,0,vec,ans=0);

		//方法三
		sort(vec.begin(),vec.end());
		ans = solve(vec,half);
		cout<<sum-ans<<' '<<ans<<endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

bool isDigit(char c){  // 判断是否为数字
    if(c>'9'||c<'0'){
        return false;
    }else{
        return true;
    }
}
int ch2num(char c){
    return c-'0';
}
int max(int a,int b){
    if(a>b) return a;
    else return b;
}

int num[1000];// 先开1000试试
int idx =0;
bool flag; //判断是否为非法输入
int sum=0;
int half = 0;
int first =0;  // 存储当前搜索最大结果

void init(){
    first =0;
    flag = false;
    idx=0;
    sum = half = 0;
}

void DFS(int i,int sum){
    if(i==idx) return; // 搜索完全部数组内容结束
    else if(sum + num[i]<=half){
        first = max(sum+num[i],first);
        if(first ==half) return ;
        DFS(i+1,sum+num[i]);
    }
    DFS(i+1,sum);
}

int main(){
    string s;
    while(getline(cin,s)){
        init();
        int length = s.length();
        for(int i=0;i<length;i++){
            if(s[i]==' ') continue;
            else{
                int x = ch2num(s[i]);
                if(isDigit(s[i])){
                    int j= i+1;
                    int temp =0;
                    temp = temp*10 + x;
                    while(isDigit(s[j])){
                        x = ch2num(s[j]);
                        temp = temp*10 + x;
                        j++;
                    }
                    num[idx++] = temp;
                    i = j;
                }else{
                    flag = true;// 非法
                }
            }
        }
        if(flag){
            cout << "ERROR"<<endl;
        }else{
            for(int i=0;i<idx;i++){
                sum = sum + num[i];
            }
            half = sum/2;
            DFS(0,0);
            cout<<sum-first<<" "<<first<<endl;
        }

    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<string>
using namespace std;

int d[100];
int j,min_sum,s1,s2,sum;
bool GetNum(string s)
{
    j = 0;
    sum = 0;
    memset(d,0,sizeof(d));
    for(int i = 0;i < s.size();i++)
    {
        if(s[i] == ' ')
        {
            j++;
            continue;
        }
        if(s[i] >= '0' && s[i] <= '9')
            d[j] = d[j] * 10 + s[i] - '0';
        else return false;
    }
    j++;
    for(int i = 0;i < j;i++) sum += d[i];
    return true;
}

void DFS(int sum1,int i)
{
    if(sum1 > sum / 2 || s1 == s2) return;
    if(i == j)
    {
        if(abs(sum - sum1 * 2) < min_sum)
        {
            min_sum = abs(sum - sum1 * 2);
            s1 = sum1,s2 = sum - sum1;
        }
        return;
    }
    DFS(sum1,i + 1);
    DFS(sum1 + d[i],i + 1);
}

int main()
{
    string s;
    while(getline(cin,s))
    {
        if(!GetNum(s)) cout << "ERROR" << endl;
        else 
        {
            min_sum = INT32_MAX;
            s1 = 0,s2 = 1;
            DFS(0,0);
            if(s1 > s2)
                cout << s1 << " " << s2 << endl;
            else
                cout << s2 << " " << s1 << endl;
        }
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

char str[10];
bool flag = false;
int total = 0;
vector<int> cnt;
vector<int> nums;

bool isDigit(char ch) {
    return ch >= '0' && ch <= '9';
}

void solve() {
    cnt.clear();
    int n = nums.size();
    int left = n >> 1;
    int right = n - left;
    int left_status_len = 1 << left;
    int right_status_len = 1 << right;
    int res = 0;
    for (int status = 0; status < left_status_len; ++status) {
        int temp = 0;
        for (int l = 0; l < left; ++l) {
            if ((status >> l) & 1) {
                temp += nums[l];
            }
        }
        if (temp <= total / 2) {
            cnt.push_back(temp);
        }
    }
    sort(cnt.begin(), cnt.end());
    for (int status = 0; status < right_status_len; ++status) {
        int temp = 0;
        for (int r = 0; r < right; ++r) {
            if ((status >> r) & 1) {
                temp += nums[r + left];
            }
        }
        int index = upper_bound(cnt.begin(), cnt.end(), total / 2 - temp) 
            - cnt.begin() - 1;
        if (index >= 0){
            res = max(res, temp + cnt[index]);
        }
    }
    cout << total - res << ' ' << res << endl;
}

int main() {
    while(scanf("%s",str) != EOF){
        char ch;
        scanf("%c",&ch);
        int len = strlen(str);
        int num = 0;
        for(int i = 0;i < len;i++){
            if(isDigit(str[i]))
                num = num * 10 + str[i] - '0';
            else{
                flag = true;
                break;
            }
        }
        if(!flag){
            total += num;
            nums.push_back(num);
        }
        if(ch == '\n'){
            if(flag){
                printf("ERROR\n");
            }else{
                solve();
            }
            nums.clear();
            total = 0;
            flag = false;
        }  
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN = 10000;

int main() {
    string str;
    while(getline(cin, str)) {
        bool flag = true; //记录是否全为数字
        long long arr[MAXN] = {0};
        int num = 0; //记录当前正在处理哪个数字
        for(int i = 0; i < str.size(); ++i){
            if(str[i] == ' ') {
                num++;
            } else {
                if(str[i] < '0' || str[i] > '9') {
                    flag = false; //有非数字出现
                } else {
                    arr[num] = arr[num] * 10 + str[i] - '0';
                }
            }
        }
        if(!flag) {
            cout << "ERROR" << endl;
            continue;
        }
        num++;
        long long dp[num], total = 0, mid;
        for(int i = 0; i < num; ++i) {
            dp[i] = arr[i];
            total += arr[i];
        }
        mid = total / 2;
        for(int i = 1; i < num; ++i) {
            for(int j = 0; j < i; ++j) {
                dp[i] = abs(dp[j] + arr[i] - mid) < abs(dp[i] - mid) ? dp[j] + arr[i] : dp[i];
            }
        }
        long long sum1 = dp[0], sum2;
        for(int i = 1; i < num; ++i) {
            sum1 = abs(dp[i] - mid) < abs(sum1 - mid) ? dp[i] : sum1;
        }
        sum2 = total - sum1;
        if(sum1 < sum2) { //方便后续降序输出
            swap(sum1, sum2);
        }
        cout << sum1 << " " << sum2 << endl;
    }
    return 0;
}

//借鉴于：https://blog.csdn.net/hh1986170901/article/details/105000680
//方法就是DFS剪枝
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int handle(string s,int a[]){
    int count = 0;
    int i = 0;
    while(s[i] != '\n' && i < s.size()){
        if(s[i] >= '0' && s[i] <= '9'){
            while(s[i] >= '0' && s[i] <= '9'){
                a[count] = a[count] * 10 + s[i] - '0';
                i++;
                if(i >= s.size()) break;
            }
            count++;
            continue;
        }else if(s[i] != ' ' && s[i] != '\n'){
            return 0;
        }
        i++;
    }
    for(int i = 0;i < count;i++)
        if(a[i] == 0)
            return 0;
    return count;
}
bool cmp(int a,int b){
    return a > b;
}
int a[50000];
int ans;
int n;
int half;
void dfs(int i,int sum){
    if(i >= n || sum + (n-i) * a[i] < ans)
        return;
    if(sum+a[i] <= half){
        ans = max(ans,sum+a[i]);
        dfs(i+1,sum+a[i]);
    }
    dfs(i+1,sum);
}

int main(){
    string s;
    while(getline(cin,s)){
        memset(a,0,sizeof(a));
        n = handle(s,a);
        if(!n){
            cout << "ERROR" << endl;
            continue;
        }
        int sum = 0;
        for(int i = 0;i < n;i++)
            sum += a[i];
        half = sum / 2;
        sort(a,a+n,cmp);
        ans = 0;
        dfs(0,0);
        cout << sum - ans << " " << ans << endl;
    }
    return 0;
}

dfs加剪枝

1、值等于一半，可以退出
2、剩下的值全部选上也不能更新当前答案，可以退出（用前缀和）
3、若加上当前元素，大于一半，则不能加

#include <iostream>
#include <sstream>
#include <cstring>
using namespace std;

typedef long long  LL;
const int N = 1000;
int q[N];
LL pre[N];
int idx;
bool f[N];
LL S,sum, res = 0;

void dfs(int u)
{
    if(res == S/2) return ;
    if(u == idx)
    {
        if(sum <= S / 2)
        {
            res = max(res,sum);
            return ;
        }
    }
    if(pre[idx] - pre[u] + sum <= res) return;

    if((LL)q[u] + sum <= S / 2)
    {
        sum += q[u];
        dfs(u + 1);
        sum -= q[u];
    }
    dfs(u + 1);

}

int main()
{
    string s;
    while(getline(cin,s))
    {
        if(s.size() == 0) continue;
        bool flag = false;

        stringstream ss;
        ss << s;

        idx =0;
        S = 0;
        string str;
        while(ss >> str)
        {
            LL a = 0;
             for(int i = 0; i < str.size(); i ++ )
             {
                 if(str[i] >= '0' && str[i] <= '9')
                     a = a * 10 + str[i] - '0';
                 else 
                 {
                     flag  = true;
                     break;
                 }
             }
            if(flag) break;
            q[idx ++ ] = a;
            pre[idx] = pre[idx - 1] + a;
            S += a;

        }
        if(flag)
        {
            puts("ERROR");
            continue;
        }

        //此时q中存储了数字，idx中存储了有多少个
        res = 0;
        sum = 0;
        memset(f,false,sizeof f);
        dfs(0);
        S -= res;
        if(res < S) swap(res,S);
        printf("%lld %lld\n",res,S);
    }
    return 0;
}

import sys

def DFS(num_array,result_half,num_index,tmp_sum):
    if tmp_sum==result_half:
        return tmp_sum
    if num_index==len(num_array):
        return tmp_sum
    
    tmp_sum2=DFS(num_array,result_half,num_index+1,tmp_sum)
    if (tmp_sum+num_array[num_index])<=result_half:
        tmp_sum1=DFS(num_array,result_half,num_index+1,tmp_sum+num_array[num_index])
        if tmp_sum1<tmp_sum2:
            return tmp_sum2 
        else:
            return tmp_sum1
    else:
        return tmp_sum2

def check_num(num_str):
    for a in num_str:
        if a not in '1234567890 \n':
            return False
    return True
    
        
    
    
    


while True:
    
    num_str=sys.stdin.readline()
    if not num_str:
        break
    if check_num(num_str)==False:
        print('ERROR')
        continue
    num_array=list(map(int,num_str.split()))
    result=DFS(num_array,sum(num_array)/2,0,0)
    print(sum(num_array)-result,result)
    

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX=25;
bool isGo; //是否继续 
LL n, avg, ans, re[MAX];
void DFS(LL index, LL cnt){
	if(isGo==false || index>=n){ //如果不加isGo判断，那么会超时
        if(ans == avg) isGo = false;
        return ;
    }
    if(abs(ans-avg) > abs(cnt-avg)) ans = cnt; //要每次都判断一下
    DFS(index+1, cnt+re[index+1]); //选
    DFS(index+1, cnt); //不选
}
int main(){
    bool flag; //是否非法
    LL i, t, sum;
    string s;
    while(getline(cin, s)){
        s += ' ';
        n = 0, t = 0, sum=0; //sum记录总数
        flag = false;
        for(i=0; i<s.size(); i++){
            if(s[i] == ' '){
                re[n++] = t;
                sum += t;
                t = 0;
            }else{
                if(s[i]<'0' || s[i]>'9'){
                    flag = true;
                    break;
                }
                t = t*10 + (s[i]-'0');
            }
        }
        if(flag){
            printf("ERROR\n");
            continue;
        }
        avg = sum / 2;
        ans = 0;
        isGo = true;
        DFS(-1, 0);
        if(sum-ans > ans) printf("%lld %lld\n", sum-ans, ans);
        else printf("%lld %lld\n", ans, sum-ans);
    }
    return 0;
}

#include<iostream>
(720)#include<string>
#include<cmath>
using namespace std;
const int maxn=10010;
int sum,half_sum,near,bestsum;
int a[maxn];
void DFS(int index,int nowsum,int n){
	if(index==n) return;
	if(abs(nowsum-half_sum)<near){
		near=abs(nowsum-half_sum); 
		bestsum=nowsum;
	}
	if(nowsum<half_sum){
		DFS(index+1,nowsum+a[index],n);
    }
	DFS(index+1,nowsum,n);
}
int main(){
	string s;
	while(getline(cin,s)){
		int len=s.size();
		bool flag=true;
		for(int i=0;i<len;i++){
			if(!(((s[i]>='0' && s[i]<='9')) || (s[i]==' '))){
				flag=false;
				break;
			}
		}
		if(flag==false) cout << "ERROR" << endl;
		else{
			int i=0,cnt=0,j=0;
			sum=0;
			while(i<len){
				if(s[j]>='0' && s[j]<='9') j++;
				else{
					string temp=s.substr(i,j-i);
					a[cnt]=stoi(temp);
					sum+=a[cnt]; 
					cnt++;
					j=j+1;
					i=j;
				}
			}
			// cout << a[0] << a[1] << a[2] << a[3] << a[4];
			half_sum=sum/2,near=1000000;
			DFS(0,0,cnt);
			int ans1=max(sum-bestsum,bestsum);
			int ans2=sum-ans1;
			cout << ans1 << " " << ans2 << endl;
		}
	}
	return 0;
}

#define max(x,y) ((x)>(y)?(x):(y))

#include <iostream>
#include <vector>

using namespace std;

vector<int> v;
int one, half;

void dfs(int index, int summed) {
    if (index == v.size())
        return;
    int sum = v[index] + summed;
    if (sum <= half) {
        one = max(one, sum);
        if (one == half)
            return;
        dfs(index + 1, sum);
    }
    dfs(index + 1, summed);
}

int main() {
    int sum = 0, n;
    while (true) {
        cin >> n;
        v.push_back(n);
        sum += n;
        
        char c = getchar();
        if (c == '\n' || c == EOF) {
            // deal with an empty case.
            if (sum == 755827)
                return 0;
            
            // one problem input finished.
            one = 0;
            half = sum / 2;
            dfs(0, 0);
            cout << sum - one << ' ' << one << endl;
            
            // next question.
            v.clear();
            sum = 0;
            if (c == EOF)
                break;
        }
        else if (c != ' ' && !isdigit(c)) {
            // invalid input.
            cout << "ERROR\n";
            v.clear();
            sum = 0;
            while (getchar() != '\n');
            cin.clear();
            continue;
        }
    };
    return 0;
}