HDU1059 二进制拆分优化多重背包

 /*问你能不能将给出的资源平分成两半,那么我们就以一半为背包,运行多重背包模版
但是注意了,由于个数过大,直接运行会超时,所以要用二进制拆分每种的个数*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int w[],vr[],dp[];
int a[],v[];
int numw;
void cf(int n,int ok)
{
int i,j,sum,e;
e=sum=;
while(sum<=n)
{
vr[numw]=v[ok];
w[numw++]=e;
e*=;
sum+=e;
}
if(n-(sum-e)>)
{
w[numw]=n-(sum-e);
vr[numw]=v[ok];
numw++;
}
}
int main()
{
int i,j,n,m,k;
int n1,n2,n3,n4,n5,n6;
int cas=;
while(scanf("%d%d%d%d%d%d",&n1,&n2,&n3,&n4,&n5,&n6)!=EOF)
{
if(n1== && n2== && n3== && n4== && n5== && n6==) break;
int num=;
if(n1!=) { a[num]=n1; v[num++]=;}
if(n2!=) { a[num]=n2; v[num++]=;}
if(n3!=) { a[num]=n3; v[num++]=;}
if(n4!=) { a[num]=n4; v[num++]=;}
if(n5!=) { a[num]=n5; v[num++]=;}
if(n6!=) { a[num]=n6; v[num++]=;}
int sum=;
//printf("%d\n",num);
for(i=;i<num;i++)
{
sum=sum+a[i]*v[i];
}
if(sum==) break;
if(sum%)
{
printf("Collection #%d:\n",++cas);
printf("Can't be divided.\n\n");
continue;
}
numw=;
for(i=;i<=sum/;i++)
dp[i]=;
for(i=;i<num;i++)
{
cf(a[i],i);
}
for(i=;i<numw;i++)
for(j=sum/;j>=w[i]*vr[i];j--)
dp[j]=max(dp[j],dp[j-w[i]*vr[i]]+w[i]*vr[i]);
printf("Collection #%d:\n",++cas);
if(dp[sum/]==sum-dp[sum/]) printf("Can be divided.\n\n");
else printf("Can't be divided.\n\n");
}
return ;
}
上一篇:python第三方库安装和卸载


下一篇:用react重构个人网站 3-22