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; 
}