poj 1014 Dividing

Description

Input

Output

Sample Input

1 0 1 2 0 0 
1 0 0 0 1 1 
0 0 0 0 0 0 

Sample Output

Collection #1:
Can‘t be divided.

Collection #2:
Can be divided.

用多重背包可以做，貌似搜索也行，但要从大往小的地方搜。

#include"stdio.h"
#include"string.h"
#define N 120005
int num[10],w[10];
int v;
int f[N];
int max(int a,int b)
{
	return a>b?a:b;
}
void zero(int c,int w)
{
	int i;
	for(i=v;i>=c;i--)
		f[i]=max(f[i],f[i-c]+w);
}
void comple(int c,int w)
{
	int i;
	for(i=c;i<=v;i++)
		f[i]=max(f[i],f[i-c]+w);
}
void multi(int c,int w,int num)
{
	if(c*num>=v)
		comple(c,w);
	else
	{
		int k=1;
		while(k<num)
		{
			zero(k*c,k*w);
			num-=k;
			k*=2;
		}
		zero(num*c,num*w);
	}
}
int main()
{
	int i,Case=1;
	while(scanf("%d",&num[1]))
	{
		v=num[1];
		for(i=2;i<=6;i++)
		{
			scanf("%d",&num[i]);
			v+=num[i]*i;
		}
		if(v==0)
			break;
		printf("Collection #%d:\n",Case++);
		if(v%2==1)
		{
			printf("Can‘t be divided.\n\n");
			continue;
		}
		v/=2;
		memset(f,0,sizeof(f));
		for(i=1;i<7;i++)
		{
			if(num[i]==0)
				continue;
			multi(i,i,num[i]);
		}
		int flag=0;
		if(f[v]==v)
			printf("Can be divided.\n\n");
		else
			printf("Can‘t be divided.\n\n");
	}
	return 0;
}

dfs代码：

#include"stdio.h"
#include"string.h"
#define N 7
int num[N],v,flag;
void dfs(int i,int sum)
{
	if(flag)
		return ;
	if(sum==v)
	{
		flag=1;
		return ;
	}
	for(;i>0;i--)
	{
		if(num[i])          //开始用while竟然出不来了！！
		{
			if(sum+i<=v)   
			{
				num[i]--;         //先改变值，再进行下一层搜索
				dfs(i,sum+i);
				if(flag)       //剪枝
					return ;
			}
		}
	}
	return ;
}
int main()
{
	int i,Case=1;
	while(scanf("%d",&num[1]))
	{
		v=num[1];
		for(i=2;i<N;i++)
		{
			scanf("%d",&num[i]);
			v+=num[i]*i;
		}
		if(v==0)
			break;
		printf("Collection #%d:\n",Case++);
		flag=0;
		if(v%2==0)
		{
			v/=2;
			dfs(6,0);
		}
		if(flag)
			printf("Can be divided.\n\n");
		else
			printf("Can‘t be divided.\n\n");
	}
	return 0;
}

poj 1014 Dividing,布布扣,bubuko.com

poj 1014 Dividing

原文：http://blog.csdn.net/u011721440/article/details/24926625