学步园

#include <stdio.h>  
#include <string.h>  
#define Size 60005  
#define Max(a,b) a>b?a:b  
int sum;  
int dp[Size];  
/*01背包*/  
void ZeroOnePack(int cost,int weight)  
{  
	int i;  
	for(i = sum;i>=cost;i--)  
		dp[i] = Max(dp[i],dp[i-cost]+weight);  
}  
/*完全背包*/  
void CompletePack(int cost,int weight)  
{  
	int i;  
	for(i=cost;i<=sum;i++)  
		dp[i] = Max(dp[i],dp[i-cost]+weight);  
}  
/*多重背包*/  
void MulPack(int cost,int weight,int count)  
{  
	int i;  
	if(cost*count>=sum)  
	{  
		CompletePack(cost,weight);  
		return ;  
	}  
	i = 1;  
	/*二进制划分*/  
	while (i<count)  
	{  
		ZeroOnePack(i*cost,i*weight);  
		count-=i;  
		i<<=1;  
	}  
	ZeroOnePack(count*cost,count*weight);  
}  
int main()  
{  
	int num[7],no = 1,i;  
	while (1)  
	{  
		sum = 0;  
		for(i=1;i<=6;i++)  
		{  
			scanf("%d",&num[i]);  
			sum+=num[i]*i;  
		}  
		if(!sum)  
			break;  
		if(sum&1)  
			printf("Collection #%d:\nCan't be divided.\n\n",no++);  
		else  
		{  
			sum>>=1;  
			for(i=0;i<=sum;i++)  
				dp[i] = 0;  
			for(i=1;i<=6;i++)  
				if(num[i])  
					MulPack(i,i,num[i]);  
			if(dp[sum] == sum)  
				printf("Collection #%d:\nCan be divided.\n\n",no++);  
			else  
				printf("Collection #%d:\nCan't be divided.\n\n",no++);  
		}  
	}  
	return 0;  
}  

2. 母函数版本

#include <iostream>
using namespace std;
int main()
{	
	int cnt[7];
	int p[7];
	for(int i = 0; i <= 6; i++)
		p[i] = i;
	int t = 0; 
	while(cin >> cnt[1] >> cnt[2] >> cnt[3] >> cnt[4] >> cnt[5] >> cnt[6],
		cnt[1] || cnt[2] || cnt[3] || cnt[4] || cnt[5] || cnt[6])
	{
		t++;
		int Max = 0;
		for(int i = 1; i <= 6; i++)
		{
			cnt[i] %= 30; //重点，不加这句会超时
			Max += cnt[i] * p[i];
		}
		if(Max % 2)
		{
			printf("Collection #%d:\n", t);
			printf("Can't be divided.\n\n");
			continue;
		}
		Max = Max / 2;
		int *c1 = new int[Max + 1];
		int *c2 = new int[Max + 1];
		for(int i = 0; i < Max + 1; i++)
		{
			c1[i] = 0;
			c2[i] = 0;
		}

		for(int i = 0; i <= cnt[1]; i++)
		{
			c1[i] = 1;
			c2[i] = 0;
		}
		for(int i = 2; i <= 6; i++)
		{
			for(int j = 0; j <= Max; j++) 
			{
				int num = cnt[i] * p[i];
				for(int k = 0; k <= num && k + j <= Max; k += p[i])
				{
					c2[k+j] += c1[j];
				}
			}
			for(int j = 0; j <= Max; j++)
			{
				c1[j] = c2[j];
				c2[j] = 0;
			}
			if(c1[Max])
				break;
		}
		int flag = 0;
		if(c1[Max] != 0)
			flag = 1;
		delete [] c1;
		delete [] c2;
		printf("Collection #%d:\n", t);
		if(flag == 0)
			printf("Can't be divided.\n\n");
		else
			printf("Can be divided.\n\n");
	}
	return 0;
}