| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
运用多重背包来做 做之前先了解poj1837的做法这个题就相对来说简单了
#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator