#include<iostream> #include<string> #include<vector> using namespace std; int main(void) { int n; while(cin>>n) { int *a=new int[n]; int sum=0; for(int i=0;i<n;i++) { cin>>a[i]; sum+=a[i]; } vector<vector<int>>dp(n,vector<int>(sum,0)); dp[0][0]=1; for(int i=0;i<n;i++) { for(int j=n/2;j>=0;j--) { for(int k=sum-a[i];k>=0;k--) { if(dp[j][k]==1) { dp[j+1][k+a[i]]=1; } } } } int min; if(n%2==0) { for(int i=sum/2;i>=0;i--) { if(dp[n/2][i]) { min=i; break; } } } else { for(int i=sum/2;i>=0;i--) { if(dp[n/2][i]==1||dp[n/2+1][i]==1) { min=i; break; } } } cout<<min<<' '<<sum-min<<endl; } return 0; }
全部评论
(0) 回帖