#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const long MAX = 2000000;

bool dp[MAX+1];

int main()
{

        int n;
        long k,sum=0,t;
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        dp[0]=true;
        for(int i=0;i<n;i++)
        {
                scanf("%ld",&k);
                sum+=k;
                for(long j=sum/2;j>=0;j--)
                        if(dp[j]&&j+k<MAX/2)
                                dp[j+k]=true;
        }
        for(t=sum/2;dp[t]==false;t--);
        printf("%d\n",sum-2*t);
        system("pause");
        return 0;
}

Edited by author 20.05.2010 22:39