Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

运用多重背包来做 做之前先了解poj1837的做法这个题就相对来说简单了

Posted by 0712105003 at 2009-10-16 20:35:23 on Problem 1014



#include<stdio.h>
#include<string.h>
int bag[50];
int countbag;
int num[7];
int f[3][240005];
int l[3]={0,-1,1};
int Cas=0;
int main()
{
	int i,j,k,temp,temp2;
	int total;
	//int mid;
	
	while(scanf("%d%d%d%d%d%d",num+1,num+2,num+3,num+4,num+5,num+6)&&(num[1]!=0||num[2]!=0||num[3]!=0||num[4]!=0||num[5]!=0||num[6]!=0))
	{
		countbag=1;
		total=0;
		for(i=1;i<=6;i++)
		{
			total+=num[i]*i;	
		}
		for(i=1;i<240005;i++)
		{
			f[1][i]=0;
			f[2][i]=0;
		}
		if(total%2)
		{
			printf("Collection #%d:\nCan't be divided.\n\n",++Cas);
			continue;
		}
		memset(bag,0,sizeof(bag));
		for(i=1;i<=6;i++)
		{
			temp2=num[i]+1;
			k=1;
			while((temp2>>k))
				k++;
			for(j=0;num[i]>=(1<<j)&&j<k-1;j++)
			{
				num[i]-=1<<j;
				bag[countbag++]=i*(1<<j);//rongliang
			}
			if(num[i])
			{
				bag[countbag++]=i*num[i];//rongliang
			}
		}
	//	for(i=1;i<countbag;i++)
	//		printf("%d ",bag[i]);
//		printf("\n");
	
		for(j=1;j<=2;j++)
		{
			f[1][120000+bag[1]*l[j]]++;
//			printf("%d  %d\n",j,120000+bag[1]*l[j]);
		}
	//	printf("**********************************\n");
		for(i=2;i<countbag;i++)
		{
			for(j=1;j<=2;j++)
			{
				for(k=0;k<240005;k++)
				{
					temp=bag[i]*l[j];
					if(k>temp)
					{
						if(f[1][k-temp])
						{
							f[2][k]+=f[1][k-temp];
			//				printf("%d %d\n",i,k);
							if(i==countbag-1&&f[2][120000])goto flag;
						}
					}
				}
			}
			for(j=0;j<240005;j++)
			{
				f[1][j]=f[2][j];
				f[2][j]=0;
			}
		}
flag:
		if(f[2][120000])
			printf("Collection #%d:\nCan be divided.\n\n",++Cas);
		else
			printf("Collection #%d:\nCan't be divided.\n\n",++Cas);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator