hdu 1709 The Balance (母函数)

点击打开链接

/*

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

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

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

其实用dp更方便,但为了练习母函数!

*/

#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;
				}
			}
		}//这里是把能有的差值用这种方式找出来
		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;
}


原文地址:https://www.cnblogs.com/yyf573462811/p/6365341.html