hdu-2844 Coins (混合背包+二进制优化)

HDU链接

题目描述：

输入描述:

输出描述:

For each test case output the answer on a single line.

输入

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

输出

8
4

题意：

有n种硬币，面额分别是Ai，每种硬币数量分别是Ci，问这些硬币能组成1~m中多少个数？
样例分析：
3 10
1 2 4 2 1 1
有2个一元，1个两元，1个四元，可以组成1,2，3，4,5，6，7,8，（9和10无法组成）能组成的一共八个

题解

如果还没学习背包问题的知识，看这里
混合背包问题
可以用二进制的方法来优化
背包问题中常见的三个元素：体积（所占容量），价值，数量
在本题中，硬币的价值即是体积也是价值A[i]，数量为硬币的数量C[i]
容量上限是m
当ca>m时，也就是一种货币的金额就超过m时，我们可以当做是完全背包，即将这种货币看做无数个，因为货币的数量乘以金额已经超过上限，所以再多也没有影响。这一部分用完全背包的做法
当ca<m时，我们就当做多重背包来做，将多重背包进行二进制优化，用01背包的解法来做
具体看代码：

（代码）

含详细讲解

#include<bits/stdc++.h> 
using namespace std;
const int maxn=1e5+5;
int dp[maxn];
int a[120],c[120];
int n,m;
void zeroone(int cost,int val)
{
   
	for(int i=m;i>=cost;i--)
	{
   
		dp[i]=max(dp[i],dp[i-cost]+val);
	}
}
void wanquanbeibao(int cost,int val)
{
   
	for(int i=cost;i<=m;i++)dp[i]=max(dp[i],dp[i-cost]+val);
}
void cal(int cost,int val,int num)
{
   
	if(cost*num>=m)wanquanbeibao(cost,val);//完全背包不必考虑数量
	else {
   
		for(int i=1;i<=num;i<<=1)
		{
   
			zeroone(i*cost,i*val);//乘以对应的系数 
			num-=i; 
		}
		zeroone(num*cost,num*val);//剩余部分处理 
	} 
}
int main()
{
   
	while(cin>>n>>m&&(n+m))
	{
   
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++)cin>>c[i];
		for(int i=1;i<=n;i++)
		{
   
			cal(a[i],a[i],c[i]);//花费，价值，数量 
		}
		int sum=0;
		for(int i=1;i<=m;i++)
		{
   
			if(dp[i]==i)sum++;
		}
		cout<<sum<<endl;
	}
	return 0;
}