tug of war

西电的VC++课上的几个通用模板,完全是可用的

#include<iostream> 
#include<string> 
#include<cmath> 
#include<cstdlib> 
using namespace std; 

int compare(const void *a,const void *b){ 
    return *(int *)b - *(int *)a; 
} 

const int maxn=101; 
const int maxm=45001; 
int s[maxn][maxm],a[maxn],b[maxm]; 

int main() 
{ 
    int i,j,k,n,sum,min; 
    while(cin>>n){ 
 
        memset(s,0,n/2*(n*450+1)*sizeof(int)); 
        sum=0; 
        for(i=1;i<=n;i++){ 
            cin>>a[i]; sum+=a[i]; 
        } 
        qsort(a,n,sizeof(int),compare); 
        b[0]=0; 
        for(i=1;i<=n;i++) b[i]=b[i-1]+a[i]; 
        s[0][0]=1; 
        for(i=1;i<=n;i++){ 
            if(i<=n/2+1){ 
               for(j=0;j<i;j++){ 
                //  for(j=i-1;j>=0;j--){ 
                    for(k=b[i-1];k>=0;k--){ 
                        if(s[j][k]) s[j+1][k+a[i]]=1; 
                    } 
                } 
            } 
        } 
        k=n/2; min=maxm; 
        for(i=1;i<=sum;i++){ 
            if(s[k][i]){ 
                j=abs(sum-i*2); 
                if(j<min) min=j; 
            } 
        } 
        if(n%2){ 
            k++; 
            for(i=1;i<=sum;i++){ 
                if(s[k][i]){ 
                    j=abs(sum-i*2); 
                    if(j<min) min=j; 
                } 
            } 
        } 
        cout<<(sum-min)/2<<" "<<(sum+min)/2<<endl; 
    } 
    return 0; 
}