HDU 1171 Big Event in HDU【多重背包||母函數】

題目：http://acm.hdu.edu.cn/showproblem.php?pid=1171

題意：将财産盡可能對半分

兩種解法：一是背包，二是母函數

            可以以财産的總和的一半為背包上限，求背包最大值。

            因為每件物品可以有很多件，是以本題為多重背包問題.

背包解法（比較快）：

#define max(a,b) ( (a) > (b) ? (a) : (b) )
#include<stdio.h>
#include<string.h>
int dp[250000],v[53],m[53];
int main()
{
    int n,i,j,sum,he,k;
	while( scanf("%d",&n)!=EOF)	
	{
		if( n <= 0 ) break;	
		he = 0;
		memset(dp,0,sizeof(dp));
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&v[i],&m[i]);	
			he += v[i]*m[i];
		}
		sum = he/2;	
		for(i=0;i<n;i++)
		{
			if( v[i] * m[i] > sum)	//完全背包
			{
				for(j=v[i];j<=sum;j++)
					dp[j] = max ( dp[j],dp[ j-v[i] ] + v[i] );
				continue;
			}
			k = 1;
			while(k < m[i])	
			{
				for(j = sum;j>=k*v[i];j--)		//01
					dp[j] = max ( dp[j],dp[ j - k*v[i] ] + k*v[i] );
				m[i] -= k;
				k <<= 1;
			}
			for(j = sum;j >= m[i]*v[i];j--)		//繼續01
				dp[j] = max ( dp[j],dp[ j - m[i] * v[i] ] + m[i] * v[i] );
		}
		printf("%d %d\n",he-dp[sum],dp[sum]);	
	}
	return 0;
}
           

母函數解法（夠慢）列出情況後，從總值的一半開始往下找，第1個系數非0就是答案

母函數：

(1+xv[0]+x2v[0]+...+xnum[0]*v[0])(1+xv[1]+x2v[1]+...+xnum[1]*v[1])...(1+xv[n]+ x 2v[n] +x 3v[n] +...+xv[n]*num[n])

#define MAX 255556	//杭電題目上在數組大小上總是個坑
int c[MAX],tc[MAX];
#include<stdio.h>
#include<string.h>
int main(){
	int time,max,i,j,k;
	int v[55],num[55];
//	freopen("in.txt","r",stdin);
	while(scanf("%d",&time)!=EOF && time >= 0){
		max = 0;
		memset(v,0,sizeof(v));
		memset(num,0,sizeof(num));

		for(i = 0; i < time; i++){
			scanf("%d%d",&v[i],&num[i]);
			max += v[i] * num[i];
		}
		for(i = 0; i <= max; i++){
			c[i] = 0;
			tc[i] = 0;
		}
		for(i = 0; i <= num[0] * v[0]; i+=v[0]){
			c[i] = 1;
		}
		for(i = 1; i < time; i++){
			for(j = 0; j <= max; j++){
				for(k = 0; k + j <= max && k <= num[i] * v[i]; k+=v[i]){
					tc[j+k] += c[j];
				}
			}
			for(j = 0; j <= max; j++){
				c[j] = tc[j];
				tc[j] = 0;
			}
		}
		for(i = max / 2; i >= 0; i--){
			if(c[i]){
				printf("%d %d\n",max-i,i);
				break;
			}
		}
	}
	return 0;
}