C++14(g++5.4) 解法, 执行用时: 938ms, 内存消耗: 476K, 提交时间: 2020-08-31 22:03:13

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 30
using namespace std;
int n;
int A,B,C;
int ans=0x7f7f7f7fl;
int sum[MAXN];
void dfs(int now){
    if(max(A,max(B,C))>ans)    return ;
    if(now==n+1){
        ans=max(A,max(C,B));
        return;
    }    
    A+=sum[now];dfs(now+1);A-=sum[now]; 
    B+=sum[now];dfs(now+1);B-=sum[now]; 
    C+=sum[now];dfs(now+1);C-=sum[now];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&sum[i]);
    dfs(1);
    cout<<ans;
}

C++11(clang++ 3.9) 解法, 执行用时: 33ms, 内存消耗: 4092K, 提交时间: 2020-09-01 12:50:40

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e3+5;
int n,sum;bool dp[N][N];
int main(){
	scanf("%d",&n);dp[0][0]=true;
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);sum+=x;
		for(int j=sum;~j;j--)for(int k=sum;~k;k--){
			if(j>=x)dp[j][k]|=dp[j-x][k];
			if(k>=x)dp[j][k]|=dp[j][k-x];
		}
	}
	for(int i=0;i<=sum;i++)for(int j=0;j<=sum;j++)if(dp[i][j]&&i>=j&&j>=sum-i-j){printf("%d\n",i);return 0;}
	return 0;
}