poj 1742Coins(混合背包)

           水题……

#include<stdio.h>
#include<string.h>
int n, m;
int value[101], num[101];
int dp[100001];
void zero_p(int i)
{
	int j;
	for(j=m; j>=value[i]; j--)
		dp[j]+=dp[j-value[i]];
}

void duo_p(int i)
{
	int j, k;
	for(k=1; k<=num[i]; k*=2)
	{
		num[i]-=k;
		for(j=m; j>=k*value[i]; j--)
			dp[j]+=dp[j-k*value[i]];
	}
	if(num[i]>0)
	{
		k=num[i];
		for(j=m; j>=k*value[i]; j--)
		    dp[j]+=dp[j-k*value[i]];
	}
}

void wu_p(int i)
{
	int j;
	for(j=value[i]; j<=m; j++)
		dp[j]+=dp[j-value[i]];
}
int main()
{
   int i, number;
   while( scanf("%d %d", &n, &m) && n)
   {
	    memset(dp, 0, sizeof(dp));
		dp[0]=1;
		number=0;
        for(i=1; i<=n; i++)
			scanf("%d", value+i);
		for(i=1; i<=n; i++)
				scanf("%d" ,num+i);
		for(i=1; i<=n; i++)
		{
			if(num[i]==1)
				zero_p(i);
			else if( num[i]*value[i]<=m )
				duo_p(i);
			else if( num[i]*value[i]>m )
				wu_p(i);
		}
		for(i=1; i<=m; i++)
		{
			if( dp[i] )
				number++;
		}
		printf("%dn", number);
   }
}

最后

以上就是单薄钢笔为你收集整理的poj 1742Coins(混合背包)的全部内容，希望文章能够帮你解决poj 1742Coins(混合背包)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。