【多重背包】硬币

博客主页: https://blog.csdn.net/qq_50285142欢迎点赞⭐️收藏⭐️❤️关注❤️留言  如有错误，敬请指正 一看一温习，一码一收获

题目链接：
https://www.acwing.com/problem/content/283/

给定 N 种硬币，其中第 i 种硬币的面值为 A i A_i Ai​，共有 C i C_i Ci​ 个。
从中选出若干个硬币，把面值相加，若结果为 S，则称“面值 S 能被拼成”。
求 1 ∼ M 1∼M 1∼M之间能被拼成的面值有多少个。

状态表示：
f [ j ] f[j] f[j]代表面值j是否能被表示
状态转移：
完全背包时： f [ j ]   ∣ = f [ j − a [ i ] ] f[j] space |= f[j-a[i]] f[j] ∣=f[j−a[i]]，注意从小到大枚举
分组背包时： f [ j ]   ∣ = f [ j − k ∗ a [ i ] ] f[j] space |= f[j-k*a[i]] f[j] ∣=f[j−k∗a[i]]，注意从到小枚举

当使用完全背包时，会超时。
当一个面值的硬币个数很多时，那么这方面的复杂度就会很高。但是当个数很多时，该硬币能够表示总额的最大值超过了m，就可以看成完全背包，可以无限取得情况。

当该面值得硬币表示的最大值小于等于m时,就不可以当成完全背包，那么就是多重01背包，可以使用二进制优化降低时间复杂度。

TLE代码：

#include 
#include
using namespace std;
const int N = 1e5+5;

int f[N];
int a[N],b[N],nb[10*N];
int n,m;

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		if(n==0 and m==0) break;
		for(int i=1;i<=m;i++) f[i] = 0;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++) scanf("%d",&b[i]);

		int tot = 0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=b[i];j<<=1)
			{
				nb[++tot] = j*a[i];
				b[i] -= j;
			}
			if(b[i])
				nb[++tot] = b[i]*a[i];
		}
		f[0] = 1;
		for(int i=1;i<=tot;i++)
		{
			for(int j=m;j>=nb[i];j--)
			{
				if(!f[j] && f[j-nb[i]]) 
					f[j] += f[j-nb[i]];
			}
		}

		int cnt = 0;
		for(int i=1;i<=m;i++) 
			if(f[i]) cnt++;
		printf("%dn",cnt);
	}
	return 0;
}

AC代码：

#include 
#include
using namespace std;
const int N = 1e5+5;

int f[N];
int a[N],b[N],nb[10*N];
int n,m;

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		if(n==0 and m==0) break;
		for(int i=1;i<=m;i++) f[i] = 0;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++) scanf("%d",&b[i]);
		f[0] = 1;
		for(int i=1;i<=n;i++)
		{
			if(a[i]*b[i]>m)
			{
				for(int j=a[i];j<=m;j++)
					f[j] |= f[j-a[i]];
			}
			else
			{
				for(int j=1;j<=b[i];j<<=1)
				{
					for(int k=m;k>=j*a[i];k--)
						f[k] |= f[k-a[i]*j];
					b[i] -= j;
				}
				if(b[i])
					for(int j=m;j>=b[i]*a[i];j--)
						f[j] |= f[j-b[i]*a[i]];
			}
		}
		int cnt = 0;
		for(int i=1;i<=m;i++) 
			if(f[i]) cnt++;
		printf("%dn",cnt);
	}
	return 0;
}

C++ STL详解，超全总结(快速入门STL) 李【期末复习】c++知识点大回顾，八篇文章让你永不破防（一）区间贡献问题习题详解