学步园

多重背包问题，求硬币可以有多少种组合(价值要小于m)

#include<stdio.h>
#include<string.h>
int dp[100010];
int main()
{
	int i,j,n,m,cont[1001],num[1001],ans,k;
	while(scanf("%d%d",&n,&m),(n||m))
	{
		for(i=0;i<n;i++)
			scanf("%d",&cont[i]);
		for(i=0;i<n;i++)
			scanf("%d",&num[i]);
		memset(dp,0,sizeof(dp));
		dp[0]=1;
		for(i=0;i<n;i++)
		{
			k=num[i];
			if(k*cont[i]>=m)
			{
				for(j=cont[i];j<=m;j++)
				{
					if(dp[j-cont[i]]==0)continue;
					dp[j]=1;
				}
			}
			else 
			{
				ans=1;
				while(k-ans>0)
				{
					for(j=m;j>=ans*cont[i];j--)
					{
						if(dp[j-ans*cont[i]]==0)continue;
						dp[j]=1;
					}
					k-=ans;ans=ans*2;//二进制的思想优化多重背包
				}
				if(k>0)
					for(j=m;j>=k*cont[i];j--)
					{
						if(dp[j-k*cont[i]]==0)
							continue;
						dp[j]=1;
					}
			}
		}
		int sum=0;
		for(i=1;i<=m;i++)
		{
			if(dp[i]==1)sum++;
		}
		printf("%d\n",sum);
	}
	return 0;
}