HDOJnbsp;nbsp;1709nbsp;nbsp;nbsp;Thenbsp;Balance

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1709

题目大意为由这些砝码，看不能表示的最小的重量是多少

则和个体问题在于天平的每个砝码都可以放在天平的两边

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int c1[10005],c2[10005];
int a[105],ans[10005];
int main()
{
 int i,j,n,sum;
 while(scanf("%d",&n)!=EOF)
 {
  sum=0;
  for(i=1;i<=n;i++)
  {
   scanf("%d",&a[i]);
   sum=sum+a[i];
  }
  for(i=0;i<=sum;i++)
  {
   c1[i]=0;
   c2[i]=0;
  }
  c1[0]=1;
  for(i=1;i<=n;i++)
  {
   for(j=0;j+a[i]<=sum;j++)
   {
    if(c1[j]==1)
    {
     c2[j]=1;
     c2[j+a[i]]=1;
     c2[abs(j-a[i])]=1;
    }
   }
   for(j=0;j<=sum;j++)
   {
    c1[j]=c2[j];
    c2[j]=0;
   }
  }
  int num=0;
  for(i=1;i<=sum;i++)
  {
   if(c1[i]==0)
    ans[num++]=i;
  }
  if(num==0)
  {
   printf("0\n");
   continue;
  }
  printf("%d\n",num);
  for(i=0;i<num-1;i++)
   printf("%d ",ans[i]);
  printf("%d\n",ans[num-1]);
 }
 return 0;
}
*******************************
 #include<stdio.h>
 #include<string.h>
 #define N 20000+10
 #define M 10000
 int a[N],b[N];
 int wei[100+10];
 int main()
 {
     int n,i,j,sum,count,Pe;
     while(scanf("%d",&n)==1&&n>=0)
     {
         Pe=0;
         sum=count=0;
         memset(a,0,sizeof(a));
         memset(b,0,sizeof(b));
         for(i=1;i<=n;i++)
         {
             scanf("%d",&wei[i]);
             sum+=wei[i];
         }
         a[M]=a[M+wei[1]]=a[M-wei[1]]=1;
         for(i=2;i<=n;i++)
         {
             for(j=M-sum;j<=M+sum;j++)
             {
                 b[j]+=a[j];
                 if(j-wei[i]>=M-sum)
                     b[j-wei[i]]+=a[j];
                 if(j+wei[i]<=M+sum)
                     b[j+wei[i]]+=a[j];
             }
             memcpy(a,b,sizeof(b));
             memset(b,0,sizeof(b));
         }
         for(i=1;i<=sum;i++)
             if(a[i+M]==0)
                 count++;
         printf("%d\n",count);
         if(count!=0)
         {
             for(i=1;i<=sum;i++)
                 if(a[M+i]==0)
                 {
                     Pe++;
                     if(Pe!=1)
                         printf(" ");
                     printf("%d",i);
                 }
             printf("\n");
         }
     }
     return 0;
 }