hdu 1709 The Balance （母函数）

点击打开链接

/*

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

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

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

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

*/

#include"stdio.h"#include"string.h"#define MAX  10008int 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;}}}//这里是把能有的差值用这种方式找出来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;}