poj1014——Dividing

多重背包问题。

转化为01背包问题。不过 需优化，否则会TLE。

优化部分程序中标出。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[60005];
int a[7];
int cnt;
int b[60005],c[60005];
int main()
{
	int i,sum,ca=0;
	int v;
	while(1)
	{
		sum=0;
		for(i=1;i<=6;i++)
		{
			cin>>a[i];
			sum+=a[i];
		}
		if(sum==0) break;
		printf("Collection #%d:\n",++ca);
		sum=0;
		for(i=1;i<=6;i++)
			sum+=i*a[i];
		if(sum%2!=0) 
		{
			printf("Can't be divided.\n");
		}
		else 
		{
			cnt=0;
			for(i=1;i<=6;i++)//优化部分
			{
				int k=1;
				while(a[i]-k+1>0)
				{
					b[++cnt]=i*k;
					c[cnt]=i*k;
					a[i]-=k;
					k=2*k;
				}
				if(a[i]>0)
				{
					b[++cnt]=i*a[i];
					c[cnt]=i*a[i];
				}
			}
			v=sum/2;
			memset(f,-1,sizeof(f));
			f[0]=0;
			int j;
			for(i=1;i<=cnt;i++)
				for(j=v;j>=0;j--)
				{
					if(j-b[i]>=0)
					{
						f[j]=f[j-b[i]]+c[i]>f[j]?f[j-b[i]]+c[i]:f[j];
					}
					else f[j]=f[j];
				}
			 if(f[v]==v) printf("Can be divided.\n");
			 else printf("Can't be divided.\n");
		}
		printf("\n");
	}
	return 0;
}