poj 1014 Dividing 다중 가방

제목: 가치가 1~6인 탄주가 각각 몇 개씩 있는데, 가치에 따라 균등하게 나눌 수 있느냐고 묻는다.
사고방식: 다중 가방, V는 전체 가치의 절반이고 dp[V]=V라면 균등하게 나눌 수 있다.

#include
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
void ZeroOnePack(int weight,int value,int V,int dp[])
{
	for(int v = V;v >= weight;v--)
		dp[v] = max(dp[v],dp[v-weight]+value);
}
void CompletePack(int weight,int value,int V,int dp[])
{
	for(int v = weight;v <= V;v++)
		dp[v] = max(dp[v],dp[v-weight]+value);
}
void MultiplePack(int weight,int value,int count,int V,int dp[])
{
	if(weight*count >= V)
		CompletePack(weight,value,V,dp);
	else
	{
		int k = 1;
		while(k < count)
		{
			ZeroOnePack(k*weight,k*value,V,dp);
			count -= k;
			k = k*2;
		}
		ZeroOnePack(count*weight,count*value,V,dp);
	}
}
int main()
{
	int v[6],total = 1,dp[60005];
	while(scanf("%d %d %d %d %d %d",&v[0],&v[1],&v[2],&v[3],&v[4],&v[5]))
	{
		int i,sum = 0;
		for(i = 0;i < 6;i++)
			sum += v[i]*(i+1);
		if(sum == 0) break;
		memset(dp,0,sizeof(dp));
		printf("Collection #%d:
",total++);
		if(sum%2 == 1)
		{
			printf("Can't be divided.
");
			printf("
");
			continue;
		}
		sum = sum/2;
		for(i = 0;i < 6;i++)
			MultiplePack(i+1,i+1,v[i],sum,dp);
		if(dp[sum] == sum) //        ，       
			printf("Can be divided.
");
		else
			printf("Can't be divided.
");
		printf("
");
	}
	return 0;
}