HDU 2844/POJ 1742 Coins
思路：多重背包+二进制优化
[cpp]
;
int c[110],v[110],n,m,sum;
int completepack(int a,int sum)
{
int i;
for(i=a;i<=m;i++)
{
if(dp[i-a]+a>dp[i])
{
dp[i]=dp[i-a]+a;
if(dp[i]==i) sum++;
}
}
return sum;
}
int pack01(int k,int a,int sum)
{
int i,t=k*a;
for(i=m;i>=t;i--)
{
if(dp[i]<dp[i-t]+t)
{
dp[i]=dp[i-t]+t;
if(dp[i]==i) sum++;
}
}
return sum;
}
int main()
{
int i,k;
while(scanf("%d%d",&n,&m)&&(n+m))
{
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
for(i=1;i<=n;i++)
scanf("%d",&c[i]);
memset(dp,0,sizeof(dp));
sum=0;
for(i=1;i<=n;i++)
{
if(v[i]*c[i]>=m)
sum=completepack(v[i],sum);
else
{
k=1;
int count=c[i];
while(k<count)
{
sum=pack01(k,v[i],sum);
count=count-k;
k=k<<1;
}
sum=pack01(count,v[i],sum);
}
}
printf("%d\n",sum);
}
return 0;
}
补充：软件开发 , C++ ,
