hdu 1709 The Balance （母函数）

/*

题目意思: 给你一个n，表示n个物品，下面有n个数，表示n个物品的重量，然后进行称量，每个物品只有一件，看不能称出的价值有几个，输出它，单独占一行，

当不为零时，输出所以不能称处的价值，并用空格隔开。。。

其中不能称出的价值包括：除（直接称出的）和（由直接称出的得出的差值）的剩余的价值。。ps:有点绕。。。

其实用dp更方便，但为了练习母函数！

*/

[html]  
#include"stdio.h" 
#include"string.h" 
#define MAX  10008 
int main() 
{ 
    int a[MAX],c1[MAX],c2[MAX],b[MAX]; 
    int i,j,k,n,sum; 
    while(scanf("%d",&n)!=EOF) 
    { 
        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[i*a[0]]=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]) 
            { 
                for(j=1;j<i;j++) 
                { 
                    if(c1[j]) 
                        b[i-j]=1; 
                } 
            } 
        }<span style="COLOR: #008000">//</span><span style="COLOR: #008000">这里是把能有的差值用这种方式找出来</span> 
        k=0; 
        for(i=1;i<=sum;i++) 
        { 
            if(!c1[i]&&!b[i])//将不能称出的价值存进c2中。。 
                c2[k++]=i; 
        } 
        printf("%d/n",k); 
        if(k) 
        { 
            for(i=0;i<k-1;i++) 
                printf("%d ",c2[i]); 
            printf("%d/n",c2[i]); 
        } 
    } 
    return 0; 
} 

作者：yyf573462811