PKU 2576 Tug of War

http://poj.org/problem?id=2576
n個の数字を、n/2個とn-n/2個のグループに分ける。
両方のグループの数字の和が出来るだけ近くなるようなわけ方にしたときに、両方の数字の和を求めろというような問題。

他の人の実行タイムを見る限りオーダーを少し落とせるようなのですが、ちょっとやり方がよくわからないので、こんな感じで解きました。
適当にググッて調べたいと思います。

bool dp[111][55001];
int in[100];

main(){
  int n;
  cin>>n;
  int sum=0;
  rep(i,n){
    cin>>in[i];
    sum+=in[i];
  }
  dp[0][0]=true;

  rep(i,n){
    for(int u=n-1;u>=0;--u){
      rep(nu,sum+1)if(dp[u][nu])dp[u+1][nu+in[i]]=true;
    }
  }

  int a=0,b=sum;
  rep(i,sum){
    if(!dp[n/2][i])continue;
    if(abs(b-a)>abs(sum-2*i)){
      a=i;
      b=sum-i;
    }
  }
  cout<<min(a,b)<<' '<<max(a,b)<<endl;
}