母函數。。
[cpp]
include"stdio.h"
#include"string.h"
int main()
{
int a[10008];
int b[10008];
int c1[10008];
int c2[10008];
int i,j,k;
int n,sum;
while(scanf("%d",&n)!=-1)
{
sum=0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
for(i=1;i<=sum;i++)
{
b[i]=0;
c1[i]=c2[i]=0;
}
for(i=0;i<=1;i++)
c1[a[0]*i]=1;//只有兩種情況:取或不取。
for(i=1;i<n;i++)
{
for(j=0;j<=sum;j++)
{
for(k=0;k*a[i]+j<=sum&&k<=1;k++)
c2[j+k*a[i]]+=c1[j];
}
for(j=0;j<=sum;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
for(i=sum;i>0;i--)
{
if(c1[i])//i可以被取到
{
for(j=1;j<i;j++)
{
if(c1[j])//j可以被取到
b[i-j]=1;//則i-j一定可以被取到。。
}
}
}
k=0;
for(i=1;i<=sum;i++)
{
if(!c1[i]&&!b[i])
c2[k++]=i;//c2存沒法被取到的。。
}
printf("%d\n",k);
if(k)
{
for(i=0;i<k-1;i++)
printf("%d ",c2[i]);
printf("%d\n",c2[i]);
}
}
return 0;
}
#include"stdio.h"
#include"string.h"
int main()
{
int a[10008];
int b[10008];
int c1[10008];
int c2[10008];
int i,j,k;
int n,sum;
while(scanf("%d",&n)!=-1)
{
sum=0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
for(i=1;i<=sum;i++)
{
b[i]=0;
c1[i]=c2[i]=0;
}
for(i=0;i<=1;i++)
c1[a[0]*i]=1;//只有兩種情況:取或不取。
for(i=1;i<n;i++)
{
for(j=0;j<=sum;j++)
{
for(k=0;k*a[i]+j<=sum&&k<=1;k++)
c2[j+k*a[i]]+=c1[j];
}
for(j=0;j<=sum;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
for(i=sum;i>0;i--)
{
if(c1[i])//i可以被取到
{
for(j=1;j<i;j++)
{
if(c1[j])//j可以被取到
b[i-j]=1;//則i-j一定可以被取到。。
}
}
}
k=0;
for(i=1;i<=sum;i++)
{
if(!c1[i]&&!b[i])
c2[k++]=i;//c2存沒法被取到的。。
}
printf("%d\n",k);
if(k)
{
for(i=0;i<k-1;i++)
printf("%d ",c2[i]);
printf("%d\n",c2[i]);
}
}
return 0;
}