代码见下:

#include<bits/stdc++.h>
using namespace std;
int dp[51][500001],N,a[101],sum=0;
int maxt(int a,int b,int c){
	return max(max(a,b),c);
}
int main(){
	cin>>N;
	for(int i=1;i<=N;i++){
		cin>>a[i];
		sum+=a[i];
	}
	for(int i=1;i<=N;i++){
		for(int j=0;j<=sum;j++){
		    if(j>=a[i]){
		        dp[i][j]=maxt(dp[i-1][j],dp[i-1][j-a[i]]+a[i],dp[i-1][j+a[i]]);
		    }else{
		        dp[i][j]=maxt(dp[i-1][j],dp[i-1][j-a[i]]+a[i],dp[i-1][a[i]-j]+j);
		    }
		}
	}
	cout<<dp[N][0]<<endl;
    return 0;
}

记录：https://www.luogu.com.cn/record/160524917